I detta dokument anser vi att de minskande en källa kortaste vägar (SSSP) problem, där givet en graf G och en källa nod s målet är att upprätthålla kortaste avstånd mellan s och alla andra noder i G under en sekvens av online kontrariska kanter raderingar. I deras seminal arbete, Even och Shiloach [JACM 1981] presenterade en exakt lösning på problemet i oviktade grafer med endast O (mn) total uppdateringstid över alla edge raderingar. Deras klassiska algoritm var toppmodern för det minskande SSSP problemet i tre decennier, även när ungefär kortaste vägar är tillåtna. Den första förbättringen över Even-Shiloach algoritmen gavs av Bernstein och Roditty [SODA 2011], som för fallet med en oviktad och oriktad graf presenterade en (1 + )-ungefärlig algoritm med konstant frågetid och en total uppdateringstid av O(n 2+o(1) ). Detta arbete utlöste en serie nya resultat, kulminerar i ett nyligen genombrott av Henzinger, Krinninger och Nanongkai [FOCS 14], som presenterade en (1 + )-ungefärlig algoritm för oriktade viktade grafer vars totala uppdateringstid är nära linjär: O(m 1+o(1) log(W )), där W är förhållandet mellan den tyngsta och den lättaste eggvikten i grafen. I detta dokument utgjorde de ett stort öppet problem när det gällde att avstyra deras resultat. Fram till helt nyligen, alla kända förbättringar över Even-Shiloach algoritmen randomiserades och krävde antagandet av en icke adaptiv motståndare. I STOC 2016 visade Bernstein och Chechik den första deterministiska algoritmen för att gå längre än O(mn) total uppdateringstid: algoritmen är också (1 + )-ungefär, och har total uppdatering Tim på O(n 2 ). I SODA 2017 presenterade samma författare en algoritm med total uppdateringstid Õ(mn 3/4 ). Båda algoritmerna är dock begränsade till oriktade, oviktade grafer. Vi presenterar den första deterministiska algoritmen för viktade oriktade grafer för att gå bortom O(mn) bunden. Den totala uppdateringstiden är Õ(n 2 log(W )).
Bernstein REF förlängde senare algoritmen för täta grafer för att hantera kantvikter i [1, W ] med total uppdateringstid Õ(n 2 log W ).
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}