Vi ser över det klassiska problemet med dynamisk upprätthållande kortaste vägar mellan alla par av noder i en riktad viktad graf. De tillåtna uppdateringarna är tillägg och raderingar av noder och deras tillbud kanter. Vi ger värsta tänkbara garantier för den tid som behövs för att bearbeta en enda uppdatering (i motsats till relaterade resultat avskrivs inte uppdateringstiden över en sekvens av uppdateringar). Vårt huvudresultat är en enkel randomiserad algoritm som för alla parameter c > 1 har en värsta-fall uppdateringstid av O(cn 2+ 2 /3 log 4 /3 n) och svarar på avstånd frågor korrekt med sannolikhet 1 − 1/n c, mot en adaptiv online motståndare om grafen inte innehåller någon negativ cykel. Den bästa deterministiska algoritmen är Thorup [STOC 2005] med en uppdateringstid på i värsta fall Õ(n 2+ 3 /4 ) och antar icke-negativa vikter. Detta är den första förbättringen av detta problem under mer än ett decennium. Konceptuellt visar vår algoritm att randomisering tillsammans med en mer direkt strategi kan ge bättre gränser.
Thorup [60] gav en helt dynamisk alla-par kortaste vägar struktur med värsta fall uppdateringstid Õ(n 2,75 ), och Abraham et al. REF gav en randomiserad uppdateringstid på i värsta fall begränsad Õ(n 2+2/3 ).
Fully dynamic all-pairs shortest paths with worst-case update-time revisited
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}