Abstrakt. Detta dokument löser ett långvarigt öppet problem i fullt dynamiska algoritmer: Vi presenterar de första fullt dynamiska algoritmer som upprätthåller anslutning, bipartitet, och ungefärlig minsta spännvidd träd i polylogaritmisk tid per kant insättning eller radering. Algoritmerna är utformade med hjälp av en ny dynamisk teknik som kombinerar en ny graf sönderdelning med randomisering. De är Las-Vegas typ randomiserade algoritmer som använder enkla datastrukturer och har en liten konstant faktor. Låt n betecknar antalet noder i grafen. För en sekvens av (m 0 ) operationer, där m 0 är antalet kanter i den ursprungliga grafen, den förväntade tiden för p-uppdateringar är O( p log 3 n) (Genom papperet logaritmerna är bas 2.) för konnektivitet och tvåpartiitet. Den värsta tiden för en fråga är O(log n/log log n). För k-edge vittnesproblem ("Har avlägsnandet av k givna kanter koppla bort grafen?") Den förväntade tiden för p-uppdateringar är O( p log 3 n) och den förväntade tiden för q-frågor är O(qk log 3 n). Med tanke på en graf med k olika vikter kan minsta spännviddsträd bibehållas under en sekvens av p-uppdateringar i förväntad tid O( pk log 3 n). Detta innebär en algoritm för att upprätthålla en 1  på ungefärlig nivå av minsta spanning träd i förväntad tid O((( p log 3 n log U) / på) för p-uppdateringar, där vikterna av kanterna är mellan 1 och U.
Henzinger och King REF fick förväntad O(log 3 n) amorterad uppdateringstid och frågetid O(log n/ log log n).
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}