48 Arbeiten
Dieses Papier liefert einen kurzen und selbstständigen Beweis für Delahans Theorem, wonach jeder einfache Graph mit Knoten als induzierter Teilgraph eines Steinhaus-Graphen mit Knoten vorkommt, indem der Begriff der erzeugenden Indexmengen für Steinhaus-Dreiecke verwendet wird.
Diese Arbeit charakterisiert die Lösbarkeit von Permutations-Match-Puzzles auf -Gittern durch eine acyclische Bedingung, liefert eine Hook-Längen-Formel für die Anzahl der Lösungen und zeigt, dass das Finden minimaler Reparaturen bei einer Verallgemeinerung auf beliebige Permutationen NP-vollständig ist.
Dieser Artikel untersucht die abelsche Eigenschaft „WELLDOC" für unendliche Wörter und liefert ein Kriterium, um zu bestimmen, ob von Morphismen erzeugte Wörter diese Eigenschaft besitzen.
Die Arbeit liefert eine vollständige Charakterisierung von Intervall-Nest-Digraphen durch verbotene Muster in linearen Knotenordnungen, die als Nest-Ordnungen bezeichnet werden, und schließt damit die Übersicht über solche Charakterisierungen bei den wichtigsten Unterklassen von Intervall-Digraphen ab.
Dieser Artikel stellt einen vereinfachten und optimierten Algorithmus zur -Approximation des durchschnittlichen Grades in Graphen mit beschränkter Arboreszenz vor, der logarithmische Verluste vermeidet und eine Abfragekomplexität von erreicht.
Die Autoren präsentieren eine Erweiterung des Matrix-Baum-Theorems für gerichtete Graphen mit nicht-verschwindenden Spaltensummen durch Hinzufügen eines Wurzelknotens, nutzen dieses Ergebnis zur Herleitung eines Matrix-Wald-Theorems und wenden die Sätze auf die Zeitentwicklung diskreter Systeme sowie auf effiziente Determinantenberechnungen an.
Dieser Artikel entwickelt Werkzeuge für die quantitative Untersuchung zufälliger minimaler Spannbäume (MST) unter der Annahme, dass die Kantengewichte unabhängig und identisch oder aus beliebigen Verteilungen gezogen werden, um deren mathematische Eigenschaften zu erforschen, die bisher weniger beleuchtet sind als die gleichverteilter zufälliger Spannbäume.
Dieser Artikel untersucht die Eigenschaften der linearen Färbungszahl von Graphen und liefert verbesserte Schranken für verschiedene Graphklassen, wobei er sich auf die von Kun, O'Brien, Pilipczuk und Sullivan aufgestellte Vermutung bezieht, dass die Baumtiefe durch das Doppelte der linearen Färbungszahl beschränkt werden kann.
Diese Arbeit liefert den theoretischen Nachweis, dass das deterministische Framework -DRESS durch die Anwendung auf -Vertex-deletierte Teilgraphen die Unterscheidungskraft der -Weisfeiler-Leman-Hierarchie erreicht, wobei dies sowohl für CFI-Grafenpaare bedingungslos bewiesen als auch für allgemeine Graphen unter einer strukturellen Vermutung gezeigt wird.
Diese Arbeit untersucht die Wahrscheinlichkeit, dass eine zufällige Auswahl von -Teilmengen die Basen eines Matroids bildet, leitet asymptotische Schwellenwerte für dieses Ereignis her und verbessert damit die Abschätzungen für die Anzahl der Matroide, insbesondere im Fall, dass der Rang langsam mit wächst.
Diese Arbeit liefert den ersten vollständigen Beweis für die geschlossene Formel zur Bestimmung der P-Positionen in additiven Subtraktionsspielen im primitiv-quadratischen Regime und zeigt, dass die Nim-Wert-Folgen auf linearen Verschiebungen dieser Positionen basieren.
Diese Arbeit entwickelt explizite Formeln für das M-Polynom verschiedener Graphenprodukte (wie kartesisches, direktes und lexikografisches Produkt), um eine einheitliche strukturelle Beschreibung der Vertex-Grad-Interaktionen zu ermöglichen und bestehende Ergebnisse für gradbasierte topologische Indizes auf Polynomniveau zu erweitern.
Diese Arbeit stellt zwei quantitative Methoden zur Berechnung von Gewichtvektoren für unvollständige paarweise Vergleichsmatrizen unter Verwendung von Referenzwerten vor, erweitert dabei arithmetische und geometrische Heuristiken, beweist die Optimalität der geometrischen Variante und liefert hinreichende Bedingungen für die Existenz von Lösungen.
Die Autoren präsentieren einen FPT-Algorithmus, der das Problem der Pfadüberdeckung in ungerichteten Graphen löst und damit eine algorithmische Verallgemeinerung des Gallai-Milgram-Theorems sowie den ersten polynomiellen Nachweis für die Hamiltonizität bei Graphen mit einer Unabhängigkeitszahl von höchstens drei ermöglicht.
Die Arbeit führt blockgetrennte Überpartitionen ein, bei denen keine zwei aufeinanderfolgenden verschiedenen Teilblocke überstrichen sind, und zeigt, dass deren Zählung durch Fibonacci-Zahlen, Transfermatrizen und asymptotisches Wachstum im selben exponentiellen Maßstab wie gewöhnliche Partitionen charakterisiert wird.
Die Autoren beweisen eine abgeschwächte Version einer Vermutung von Chudnovsky et al., indem sie zeigen, dass Graphen, die und das Gitter als induzierte Minoren ausschließen, eine Baumszerlegung besitzen, deren Taschen eine beschränkte Unabhängigkeitszahl bezüglich großer Distanzen aufweisen.
Dieser Artikel führt eine umfassende Verallgemeinerung des Switching-Operators für -Graphen ein, löst damit offene Probleme von Klostermeyer, MacGillivray und Brewster, etabliert kategorientheoretische Produkte und untersucht die damit verbundenen chromatischen Zahlen, insbesondere für Wälder.
Dieser Artikel untersucht die Komplexität des Rekonfigurationsproblems für Distanz--Dominanzmengen und zeigt eine interessante Komplexitätsdichotomie auf, indem er für auf Split-Graphen polynomielle Algorithmen nachweist, während das Problem auf planaren Graphen mit maximalem Grad drei sowie auf bipartiten und chordalen Graphen weiterhin PSPACE-vollständig bleibt.
Diese Arbeit untersucht die parametrisierte Komplexität des kürzesten Pfadproblems mit positiven disjunktiven Einschränkungen und liefert Kernelisierungen sowie Fixed-Parameter-Tractability-Ergebnisse für verschiedene Parameter wie die Lösunggröße und strukturelle Eigenschaften des Zwangsgraphen.
Diese Arbeit untersucht die Machbarkeit von Quantenalgorithmen zur Lösung der 3D-heterogenen Poisson-Gleichung für Frakturströmungen, zeigt dabei zwar eine exponentielle Speicherersparnis und eine verbesserte Laufzeit gegenüber klassischen Methoden, identifiziert jedoch die begrenzte Wirksamkeit von Vorkonditionierung bei der Blockkodierung als entscheidendes Hindernis für den vollen Quantenvorteil.