Sammanfattning Vi får följande resultat relaterade till dynamiska versioner av de kortastepaterna problem: (i) Minskningar som visar att de inkrementella och decrementala single-source kortaste-pates problem, för viktade riktade eller oriktade grafer, är, i en stark mening, minst lika svårt som de statiska alla-par kortaste-pates problem. Vi får också något svagare resultat för motsvarande oviktade problem. (ii) En randomiserad fullt dynamisk algoritm för de alla-par kortaste-paterna problem i riktade oviktade grafer med en amorterad uppdateringstid på Õ(m ε n) (vi använder Õ för att dölja små poly-logaritmiska faktorer) och en värsta fall frågetid är O(n 3/4 ). iii) En deterministisk O(n 2 log n) tidsalgoritm för att konstruera en O(log n)-spanner med O(n) kanter för viktad oriktad graf på n hörn. Algoritmen använder en enkel algoritm för att stegvis underhålla en källa kortaste-sökvägar träd upp till ett visst avstånd.
Roditty och Zwick Ref överväga de inkrementella och decrementala versionerna av den enda källan kortaste vägen problem i viktade och oviktade riktade grafer.
On Dynamic Shortest Paths Problems
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}