48 articoli
Il documento presenta una dimostrazione breve e autonoma del teorema di Delahan, che afferma che ogni grafo semplice su vertici appare come sottografo indotto di un grafo di Steinhaus su vertici, ottenuta attraverso l'analisi degli insiemi di indici generatori per i triangoli di Steinhaus.
Questo articolo caratterizza i "permutation match puzzles" su griglie, dimostrando che la loro risolubilità dipende dall'assenza di cicli nel grafo dei vincoli, fornendo una formula per il numero di soluzioni e un algoritmo lineare per le riparazioni minime nel caso semplice, mentre stabilisce che il problema diventa NP-completo quando si generalizzano i vincoli a permutazioni arbitrarie.
Questo articolo studia la proprietà WELLDOC, una proprietà di tipo abeliano per parole infinite, fornendo un criterio per identificarla nelle parole generate da morfismi.
Questo lavoro fornisce una caratterizzazione completa dei digrafi nido a intervalli attraverso ordinamenti lineari dei vertici che evitano specifici pattern, denominati "nest orderings", colmando così un'importante lacuna nella classificazione delle principali sottoclassi dei digrafi a intervalli.
Questa nota presenta una versione completa e ottimizzata dell'algoritmo di Eden, Ron e Seshadhri per stimare il grado medio di grafi con arboricità limitata, eliminando le perdite logaritmiche e fornendo un'approssimazione con un numero di query pari a .
Il paper presenta una versione del teorema dell'albero matriciale che collega il determinante di una matrice alle arborescenze del suo grafo diretto, estendendo il risultato per includere somme di colonne non nulle tramite l'aggiunta di un vertice radice e applicando il teorema all'all-minors e all'evoluzione temporale di sistemi a stati discreti.
Questo articolo sviluppa strumenti per lo studio quantitativo degli alberi di copertura minimi casuali (MST), analizzando sia il caso standard con pesi indipendenti e identicamente distribuiti sia generalizzazioni che portano a misure prodotto con pesi estratti da distribuzioni arbitrarie.
Questo articolo indaga le proprietà del numero cromatico lineare, un parametro introdotto per applicazioni algoritmiche, fornendo nuovi limiti migliorati in diverse classi di grafi e contribuendo a verificare la congettura secondo cui la profondità dell'albero è limitata dal doppio di tale parametro.
Questo articolo fornisce la giustificazione teorica del framework DRESS, dimostrando che la sua variante -DRESS distingue tutte le coppie CFI e, sotto una specifica congettura strutturale, supera o eguaglia la gerarchia -WL per ogni .
Questo articolo stabilisce una soglia di probabilità precisa affinché una collezione casuale di -sottoinsiemi definisca un matroide, dimostra che tali matroidi sono quasi certamente "sparse paving" e utilizza un algoritmo greedy per migliorare le stime asintotiche sul numero di matroidi, permettendo al rango di crescere con .
Questo articolo determina la struttura completa dei valori nim per i giochi di sottrazione additiva nel regime quadratico primitivo, fornendo una dimostrazione completa della formula chiusa basata su espressioni di tipo Beatty per le posizioni P, che era stata precedentemente enunciata senza prova nella letteratura.
Questo articolo sviluppa formule esplicite e compatte per il polinomio M di diversi prodotti di grafi (diretto, cartesiano, forte, lessicografico, differenza simmetrica, disgiunzione e prodotto di Sierpiński), fornendo una descrizione strutturale unificata di come le interazioni tra i gradi dei vertici si propagano sotto tali costruzioni.
Questo articolo propone due metodi quantitativi basati su valori di riferimento per calcolare vettori di pesi da matrici di confronti a coppie incomplete, estendendo le tecniche HRE aritmetiche e geometriche, dimostrando l'ottimalità e l'esistenza della soluzione per la variante geometrica e fornendo condizioni sufficienti per quella aritmetica.
Questo lavoro risolve una questione aperta generalizzando l'algoritmo di Gallai-Milgram attraverso un approccio FPT che, per un grafo non orientato, determina in tempo polinomiale se esiste una copertura di cammini inferiore a un certo parametro o produce un insieme indipendente che certifica la non esistenza di tale copertura, includendo come sottoprodotto significativo il primo algoritmo in tempo polinomiale per il problema dell'Hamiltonianità nei grafi con numero di indipendenza limitato.
Il paper introduce e analizza le sovrappartizioni a blocchi separati, una famiglia vincolata in cui l'assenza di due blocchi consecutivi sovrallineati genera una struttura governata dai numeri di Fibonacci, permettendo di derivare rappresentazioni combinatorie, ricorrenze e un'analisi asintotica che mostra una crescita esponenziale analoga a quella delle partizioni classiche.
Il paper dimostra una versione indebolita di una congettura recente, provando che ogni grafo che esclude come minori indotti sia il grafo bipartito completo sia la griglia ammette una decomposizione ad albero in cui ogni sacchetto ha un numero di indipendenza a distanza $16(\log n + 1)$ limitato da una funzione polilogaritmica della dimensione del grafo.
Questo articolo generalizza l'operazione di switching per i grafi , risolvendo problemi aperti precedenti, dimostrando l'esistenza e le proprietà del prodotto categorico in questo contesto e determinando il numero cromatico generalizzato per le foreste mediante strumenti della teoria dei gruppi.
Il documento stabilisce una dicotomia di complessità per il problema di riconfigurazione dell'insieme dominante a distanza- (), dimostrando che è risolvibile in tempo polinomiale sui grafi split (con un algoritmo lineare sugli alberi sotto la regola ) mentre rimane -completo su grafi planari, bipartiti e cordali, estendendo così i risultati noti per il caso .
Questo articolo studia la complessità parametrizzata del problema del cammino minimo con vincoli disgiuntivi positivi, fornendo kernelizzazioni polinomiali basate sulla dimensione della soluzione e risultati di trattabilità parametrizzata basati sulle proprietà strutturali del grafo dei vincoli.
Questo studio dimostra che, sebbene l'incodifica a blocchi di un sistema di equazioni di Poisson 3D eterogenee permetta un algoritmo quantistico con complessità temporale e memoria superiori ai metodi classici, l'incapacità di migliorare il numero di condizione efficace tramite la precondizionazione separata rappresenta una limitazione significativa per l'applicazione pratica di tali algoritmi nella simulazione del flusso di fratture geologiche.