I problemet med den kortaste enskilda källan (SSSP) vill vi behålla avstånden mellan en given källa nod s och varje annan nod i en n-node m-edge graf G som genomgår kantraderingar. Även om dess statiska motsvarighet kan lösas i nära-linjär tid, detta minskande problem är mycket mer utmanande även i det oriktade oviktade fallet. I detta fall har den klassiska O (mn) totala uppdateringstiden för Even och Shiloach [16] varit den snabbast kända algoritmen i tre decennier. Till priset av en (1 + ε ) - approximation faktor, var löptiden nyligen förbättrats till n 2+o (1) av Bernstein och Roditty [9]. I den här artikeln tar vi ner körtiden till nästan linjär: Vi ger en (1 + ε )-approximationsalgoritm med m 1+o (1) förväntad total uppdateringstid, vilket ger nära linjär tid. Dessutom får vi m 1+o (1) logW tid för viktat fall, där kantvikter är heltal från 1 till W. Det enda tidigare arbetet på viktade grafer i o (mn) tid är mn 0.9+o (1) -tid algoritm av Henzinger et al. [18, 19], som fungerar för riktade grafer med kvasipolynomiska kantvikter. Den förväntade drifttiden för vår algoritm håller mot en omedveten motståndare. I motsats till tidigare resultat, som är beroende av att upprätthålla en sparsam emulator, är vår algoritm beroende av att upprätthålla en så kallad sparse (h, ε )-hop som introducerades av Cohen [12] i PRAM-litteraturen. En (h, ε )-hop uppsättning av en graf G = (V, E) är en uppsättning F viktade kanter så att avståndet mellan varje par av noder i G kan vara (1 + ε ) - ungefärlig av deras h-hop avstånd (ges av en väg som innehåller i de flesta h kanter) på G = (V, E  till F ). Vår algoritm kan upprätthålla en (n o (1), ε )-hop uppsättning av nära-linjär storlek i nära-linjär tid under kant raderingar. Det är det första i sitt slag till det bästa av vår kunskap. För att hålla ungefärliga avstånd med hjälp av detta humle set, utökar vi monotone Even-Shiloach träd av Henzinger et al. [20] och kombinera den med den avgränsade SSSP-tekniken i Bernstein [4, 5] och Mödry [27]. Dessa två nya verktyg kan vara av oberoende intresse.
Efter att ha förbättrat den totala uppdateringstiden för mindre oriktade grafer till O(n 2+o(1) ) [BR11] utvecklade Henzinger, Forster och Nanongkai en nästan linjär tidsalgoritm som tar tid O(m 1+o(1) log W ) REF för mindre viktade grafer.
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}