Deterministische dynamische Kantenfärbung

Gegeben ist ein dynamischer Graph G mit n Vertices und m Kanten, der unter Einfügungen und Löschungen von Kanten steht. Wir zeigen, wie man eine (1+) -Kantenfärbung von G ohne den Einsatz von Randomisierung aufrechterhalten kann. Genauer gesagt zeigen wir einen deterministischen dynamischen Algorithmus mit einer amortisierten Aktualisierungszeit von 2^O ^{-₁ (n) } unter Verwendung von (1+) Farben. Falls ^-1 2^O (^{0. 49 n) } gilt, dann ist unsere Aktualisierungszeit sub-polynomial in n. Während es randomisierte Algorithmen gibt, die Färbungen mit der gleichen Anzahl von Farben Christiansen STOC'23, Duan, He, Zhang SODA'19, Bhattacarya, Costa, Panski, Solomon SODA'24 in polylogarithmischer und sogar konstanter Aktualisierungszeit aufrechterhalten, ist dies der erste deterministische Algorithmus, der die gierige Schwelle von 2-1 Farben für alle Eingabegrafen unterschreitet. Auf dem Weg zu unserem Hauptergebnis zeigen wir, wie man dynamisch eine flache Hierarchie von Grad-Splittern mit sowohl Rückgriff als auch Aktualisierungszeit in n^o (1) aufrechterhalten kann. Wir glauben, dass dieser Algorithmus von eigenem Interesse sein könnte.