48 Arbeiten
Dieses Paper stellt HYGENE vor, eine bahnbrechende, auf Diffusionsmodellen basierende Methode, die durch einen schrittweisen lokalen Erweiterungsprozess realistische und vielfältige Hypergraphen generiert und damit erstmals tiefenlernbasierte Ansätze für die Hypergraph-Generierung ermöglicht.
Der Artikel untersucht eine neue Starrheitsdefinition für Polytope, bei der Kantenlängen und die Koplanarität von Flächen erhalten bleiben, während die Form der Flächen verändert werden darf, und beweist, dass konvexe Polytope in Dimension drei generisch starr sind, obwohl sie unter diesen speziellen Bedingungen flexibel sein können.
Diese Arbeit präsentiert eine vereinfachte und in moderner Terminologie verfasste Version von Ralph Seiferts 1971 veröffentlichtem Beweis, dass keine primen funktionalen Digraphen existieren.
Die Autoren zeigen, dass eine einfache exakte Methode alle klassischen TSPTW-M-Testinstanzen mit 50 oder mehr Kunden in unter zehn Sekunden löst, was beweist, dass diese Benchmarks nicht mehr repräsentativ für die Bewertung von Algorithmen sind und bei der Erstellung von Trainingsdaten für maschinelles Lernen Vorsicht geboten ist.
In diesem Artikel wird die langjährige Vermutung von Erdős über Matchings in Extremalkombinatorik bewiesen, wonach die maximale Größe einer Familie von -elementigen Teilmengen ohne paarweise disjunkte Mengen durch das Maximum zweier kanonischer Schranken beschränkt ist.
Die Arbeit beweist, dass asymptotisch fast alle vektoriellen Funktionen über endlichen Körpern triviale erweiterte-affine Stabilisatoren besitzen, was zu einer exakten asymptotischen Formel für die Anzahl der Äquivalenzklassen führt und die Wirksamkeit zufälliger Stichproben für das Design kryptografischer Primitive bestätigt.
Diese Arbeit stellt einen effizienten Algorithmus auf Basis der Spaltengenerierung vor, um das konvexe Multi-Commodity-Flow-Problem in Telekommunikationsnetzen zu lösen, bei dem die Kosten mit der Auslastung der Verbindungen konvex ansteigen, und bietet dabei Lösungen sowohl für splittbare als auch für unteilbare Flussvarianten.
Diese Arbeit bestimmt systematisch den zirkulären chromatischen Index kleiner Graphen und Multigraphen mit maximalem Grad bis 6, konstruiert unendliche Familien mit spezifischen Indexwerten und widerlegt damit Varianten der „Upper Gap-Vermutung" bezüglich der Kantenverbindlichkeit.
Diese Arbeit untersucht das Dominationspolynom des ko-maximalen Graphen , leitet explizite Formeln für bestimmte Fallkonstellationen her, analysiert deren Unimodalität und Log-Konkavität, stellt strukturelle Zusammenhänge für allgemeine her und untersucht die Wurzeln des Polynoms unter Verwendung des Satzes von Eneström–Kakeya.
Die Arbeit untersucht Max-Cut-Instanzen mit geometrisch abnehmenden Kantengewichten, identifiziert isolierte Schnitte als dominante Kandidaten für den optimalen Schnitt in einem intermediären Regime, leitet exakte Schwellenwerte für deren Dominanz her und stellt die Vermutung auf, dass diese Schnitte für hinreichend große global optimal sind.
Die Arbeit untersucht gewichtete Adjazenzspektren vollständiger multipartiter Graphen, charakterisiert Familien mit drei Eigenwerten, korrigiert frühere Ergebnisse zu Energieänderungen nach Kantenlöschung und löst ein offenes Problem bezüglich der ISI-Energie multipartiter Graphen.
Dieser Artikel identifiziert und charakterisiert drei notwendige Bedingungen sowie neue Graphklassen, für die diese Bedingungen hinreichend sind, um in polynomieller Zeit eine azyklische Orientierung mit vorgegebener Ingrad-Parität zu konstruieren, und untersucht dabei insbesondere die Inklusionsbeziehungen zwischen diesen Klassen sowie die Lösbarkeit bei kartesischen Produkten von Pfaden und Kreisen.
Die Autoren zeigen, dass für Hypergraphen, die durch kreuzfreie zusammenhängende Teilgraphen eines Wirtsgraphen mit beschränktem Geschlecht definiert sind, ein Support mit ebenfalls beschränktem Geschlecht existiert, was eine Verallgemeinerung früherer Ergebnisse für planare Graphen darstellt.
Diese Arbeit untersucht die Kantendichte von Graphen-Zeichnungen, die eine bestimmte Zellart vermeiden, und liefert für fast alle Kombinationen von Zeichnungsstil, Graphentyp und Zellart scharfe obere und untere Schranken, die zeigen, dass die Kantendichte entweder linear oder superlinear in der Anzahl der Knoten ist.
Diese Arbeit nutzt das neuartige Framework der Lokalisierung, um bekannte obere Schranken für die Anzahl von K-Cliquen in Graphen mit beschränktem Grad oder Pfadlänge zu verschärfen und die zugehörigen extremalen Graphen strukturell zu charakterisieren.
Diese Arbeit zeigt, dass für Mengen phylogenetischer Bäume mit nur geringem gemeinsamer Struktur die Anzahl der zur Darstellung notwendigen Reticulationen in einem phylogenetischen Netzwerk nahezu der trivialen Obergrenze entspricht, was durch einfache Zählargumente belegt wird.
Die Arbeit untersucht die Zustandskomplexität von -automatischen Folgen und deren linearen Teilfolgen, stellt eine Verbindung zur Subwortkomplexität her, löst eine offene Frage von Zantema und Bosma bezüglich der Eingabe im Most-Significant-Digit-First-Format und analysiert die Komplexität der Konstruktion entsprechender Automaten mittels Büchi-Arithmetik.
Dieser Artikel liefert einen vollständigen Beweis für die bereits von Abd Aziz, Rad und Kamarulhaili vorgeschlagene, aber unvollständig bewiesene obere Schranke des doppelten Dominationszahls maximaler äußerplanarer Graphen.
Die Arbeit leitet explizite Formeln für das allgemeine Positionspolynom vollständiger multipartiter Graphen her, zeigt, dass dieses Polynom für balancierte Graphen mit Teilgröße log-konkav und unimodal ist, widerlegt diese Eigenschaften jedoch für größere , und beweist zudem, dass die Unimodalität bei der Corona-Bildung für zahlreiche natürliche Graphklassen erhalten bleibt.
Die Arbeit beweist, dass die Lücke zwischen der minimalen Größe einer Booleschen Schaltung und einer Booleschen Formel über dem AIG-Basis immer 0 oder 1 beträgt, wobei ein Wert von 1 ausschließlich durch eine einzige Gatterteilung mit Fan-out 2 entsteht, sobald die Anzahl der essentiellen Variablen einen bestimmten Schwellenwert überschreitet.