Att beräkna de starkt sammankopplade komponenterna (SCC) i en graf G = (V, E) är känt för att ta endast O (m + n) tid med hjälp av en algoritm av Tarjan från 1972[SICOMP 72] där m =  på E, n =  på V. För fullt dynamiska grafer, villkorade lägre gränser ger bevis för att uppdateringstiden inte kan förbättras av polynom faktorer över recomputing SCCs från grunden efter varje uppdatering. Trots detta har betydande framsteg gjorts för att hitta algoritmer med snabb uppdateringstid för decremental grafer, dvs.. Grafer som genomgår kantradering. I detta papper presenterar vi den första algoritmen för allmänna decremental grafer som upprätthåller SCCs i total uppdateringstid Õ(m) 1, alltså bara en polylogaritmisk faktor från den optimala körtiden. Tidigare var ett sådant resultat bara känt för det speciella fallet av planar grafer [Italiano et al, STOC 17]. Vårt resultat bör jämföras med den tidigare bästa algoritmen för allmänna grafer som uppnår den totala uppdateringstiden av Chechik et.al. [FOCS 16] som förbättrades på ett genombrottsresultat som ledde till O(mn 0.9+o.1 ) total uppdateringstid av Henzinger, Krinninger och Nanongkai [STOC 14, ICALP 15]; dessa resultat förbättrades i sin tur på den långvariga gränsen av O(mn) av Roditty och Zwick [STOC 04]. Alla ovanstående resultat gäller även problemet med att nå fram till en enda källa, som kan reduceras till ett minskat underhåll av SCC. En gräns för O(mn) total uppdateringstid för minskande SSR fastställdes redan 1981 av Even och Shiloach [JACM 81]. • Teori för beräkning → Dynamiska grafalgoritmer; Konstruktion och analys av datastrukturer.
För allmänna grafer, den för närvarande bästa decremental algoritmen upprätthåller tillgänglighetsinformation i O(m log 4 n) tid REF.
Decremental strongly-connected components and single-source reachability in near-linear time
{'venue': 'STOC 2019', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}