49 articoli
Il paper introduce HYGENE, il primo metodo basato su diffusione per la generazione di ipergrafi realistici e diversificati, che utilizza un approccio di espansione locale progressiva sulla rappresentazione bipartita per modellare relazioni di ordine superiore complesse.
Questo articolo introduce un nuovo concetto di rigidità per i poliedri basato sulla conservazione delle lunghezze degli spigoli e della planarità delle facce, dimostrando che i poliedri convessi sono genericamente rigidi in dimensione tre e ipotizzando che ciò valga anche per dimensioni superiori.
Questo articolo presenta una versione semplificata e accessibile, utilizzando la terminologia moderna, della dimostrazione di Ralph Seifert del 1971 secondo cui non esistono digrafi funzionali primi.
Il paper dimostra che un metodo semplice ed esatto risolve istantaneamente le istanze di riferimento classiche del problema del commesso viaggiatore con finestre temporali, rivelando che queste non sono più rappresentative per valutare l'efficacia degli algoritmi e richiedendo cautela nella creazione di set di addestramento per il machine learning.
Questo articolo dimostra la Congettura di Erdős sulle corrispondenze, affermando che la cardinalità massima di una famiglia di sottoinsiemi di elementi di che non contiene sottoinsiemi disgiunti è limitata superiormente dal massimo tra due valori binomiali specifici.
Il documento dimostra che asintoticamente quasi tutte le funzioni vettoriali su campi finiti possiedono stabilizzatori estesi-affini banali, concludendo che le classi di equivalenza EA sono asintoticamente pari alla stima grezza e che la probabilità di equivalenza tra funzioni campionate indipendentemente è trascurabile, validando così l'uso di strategie di campionamento casuale nella progettazione di primitive crittografiche.
Questo lavoro propone un approccio algoritmico basato sulla generazione di colonne per risolvere il problema del flusso multi-prodotto con costi convessi sugli archi, gestendo efficacemente sia le varianti frazionabili che non frazionabili per ottimizzare il traffico nelle reti di telecomunicazione.
Questo articolo determina sistematicamente l'indice cromatico circolare di piccoli grafi e multigrafi con grado massimo fino a 6, costruendo famiglie infinite di tali grafi e confutando varianti della "Congettura del Gap Superiore" relative all'indice cromatico circolare.
Il presente studio analizza il polinomio di dominazione del grafo co-massimale dell'anello degli interi modulo , fornendo formule esplicite per casi specifici che dimostrano unimodalità e log-concavità, esprimendo il polinomio generale tramite sottografi indotti e stabilendo limiti per le radici di dominazione mediante il teorema di Eneström-Kakeya.
Il documento analizza una famiglia di istanze di Max-Cut su grafi completi con pesi geometrici, dimostrando l'esistenza di una struttura a soglia gerarchica che determina l'ottimalità di tagli isolati specifici in funzione del parametro di decadimento e proponendo la congettura che tali tagli siano globalmente ottimali per .
Questo articolo presenta lo spettro delle matrici di adiacenza pesate per i grafi multipartiti completi e le loro varianti a corona, caratterizza le famiglie con tre autovalori distinti, identifica le matrici intere, corregge risultati precedenti sulla diminuzione dell'energia e del raggio spettrale dopo la rimozione di un arco e risolve un problema aperto riguardante l'energia ISI nei grafi multipartiti.
Il paper definisce e caratterizza diverse classi di grafi per le quali l'esistenza di un'orientazione aciclica con parità vincolata è garantita da condizioni necessarie specifiche, fornendo inoltre algoritmi costruttivi in tempo polinomiale per risolvere il problema su tali classi, inclusi prodotti cartesiani di percorsi e cicli.
Il documento dimostra che per ipergrafi definiti da sottografi cross-free di un grafo ospite di genere limitato, è possibile costruire un supporto che mantiene anch'esso il genere limitato, generalizzando risultati precedenti su regioni non penetranti e fornendo un'analisi unificata per problemi di impacchettamento, copertura e colorazione su superfici.
Questo articolo studia la densità dei grafi ammissibili in disegni topologici privi di una specifica cella, fornendo limiti superiori e inferiori per ogni combinazione di tipo di grafo, stile di disegno e cella, e caratterizzando completamente i grafi semplici che ammettono disegni privi di celle non incidenti a incroci.
Questo articolo utilizza il framework di localizzazione per migliorare i limiti superiori esistenti sui numeri di sottografi in grafi con vincoli di grado massimo o lunghezza di cammino, fornendo inoltre caratterizzazioni strutturali dei grafi estremali che raggiungono tali limiti.
Questo articolo dimostra che per insiemi di alberi filogenetici con struttura comune quasi nulla, il numero di reticolazioni necessario per visualizzarli è prossimo al limite superiore banale, confermando che la complessità cresce linearmente con il numero di alberi fino a raggiungere un limite superiore di per insiemi sufficientemente grandi.
Questo articolo costruisce automi per riconoscere relazioni sulle sequenze -automatiche, analizza la loro complessità di stati, stabilisce una relazione tra la complessità delle parole e quella delle sottosuccessioni lineari, risolve una questione recente di Zantema e Bosma e discute la complessità computazionale della costruzione di tali automi tramite l'aritmetica di Büchi.
Questo articolo fornisce una dimostrazione completa e valida per il limite superiore del numero di doppia dominazione nei grafi outerplanari massimali, correggendo una prova precedente risultata incompleta.
Questo articolo fornisce formule esplicite per i polinomi di posizione generale di grafi multipartiti completi e corona, dimostrando che tali polinomi sono unimodali e log-concavi per partizioni bilanciate di piccole dimensioni e per diverse classi di grafi, pur lasciando aperta la questione per il caso generale.
Il documento dimostra che il divario tra la dimensione minima di un circuito booleano e quella di una formula è sempre 0 o 1, stabilendo che tale differenza unitaria deriva esclusivamente da un singolo gate con fan-out pari a 2 e fornendo condizioni precise su quando la condivisione delle sottoreti è necessaria.