Med tanke på en dynamisk digraf G = (V, E) genomgår kant raderingar och ges s  på V och konstant  på 0 <  på ≤ 1, vi anser att problemet med att upprätthålla (1 +  på)-ungefärliga kortaste väg avstånd från s till alla hörn i G över sekvensen av raderingar. Jämn och Shiloach (J. ACM'81) ger en deterministisk datastruktur för den exakta versionen av problemet i oviktade grafer med total uppdateringstid O(mn). Henzinger m.fl. (STOC'14, ICALP'15) ger en Monte Carlo datastruktur för den ungefärliga versionen med en förbättrad total uppdateringstid bundet av O(mn 0.9+o(1) log W ) med bättre gränser för tillräckligt täta och tillräckligt glesa grafer; här W är förhållandet mellan den största och minsta kanten vikt. En nackdel med deras datastruktur och i själva verket med alla tidigare randomiserade datastrukturer är att de bara arbetar mot en omedveten motståndare, vilket innebär att raderingen måste rättas i förväg. Detta begränsar dess tillämpning som en svart låda inuti algoritmer. Den första datastrukturen är Las Vegas och arbetar mot en adaptiv motståndare; den har total förväntad uppdateringstid Õ(m 2/3 n 4/3 ) 1 för oviktade grafer och Õ(m 3/4 n 5/4 log W ) för viktade grafer, 2. den andra datastrukturen är Las Vegas och förutsätter en glömsk motståndare; den har total förväntad uppdateringstid Õ( ε mn 3/2 ) för oviktade grafer och Õ(m 2/3 n 4/3 log W ) för viktade grafer, 3. den tredje datastrukturen är Monte Carlo och är korrekt w.h.p. mot en omedveten motståndare; den har totalt förväntat uppdateringstid Õ((mn) 7 log W ) = Õ(mn 3/4 log W ). Var och en av våra datastrukturer kan rapportera längden av en (1+ på)-ungefär kortaste vägen från s till någon frågevertex i konstant tid vid någon punkt under sekvensen av uppdateringar; om motståndaren är omedvetna, en fråga kan utökas för att också rapportera en sådan väg i tid proportionell mot dess längd. Vår uppdateringstider är snabbare än de av Henzinger et al. för alla graftätheter. Till exempel, när m =  på 2, vårt andra resultat förbättrar sin gräns från Õ(n 2+3/4+o(1) log W ) till Õ(n 2+1/2 ) i den oviktade inställningen och Õ(n 2+2/3 log W ) i den viktade inställningen. När m = (n) ger vårt tredje resultat en förbättring från Õ(n 1+5/6+o(1) log W ) till Õ(n 1+3/4 log W ). Dessutom är vår första datastruktur den första att förbättra på O(mn) bundet av Even och Shiloach för alla utom de glesaste grafer medan fortfarande arbetar mot en adaptiv motståndare och fungerar även i viktade grafer; detta svar ett öppet problem av Henzinger et al.
Nyligen uppnådde Probst Gutenberg och Wulff-Nilsen REF bättre körtid O(mn 3/4 log W ) (med bättre gränser för ett brett spektrum av graftätheter) och visade att det finns en algoritm med uppdateringstid O(m 3/4 n 5/4 log W ) som arbetar mot en adaptiv motståndare, men deras senare algoritm kan inte rapportera vägar.
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}