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 vägar mellan s och alla andra noder i G under en sekvens av online adversarial edge raderingar. (Vår algoritm kan också ändras för att arbeta i inkrementell inställning, där grafen initialt är tom och föremål för en sekvens av online-adversariella kantinsättningar.) I deras seminal arbete, Even och Shiloach [JACM 1981] presenterade en exakt lösning på problemet med endast O (mn) total uppdateringstid över alla edge raderingar. Senare papper presenterade villkorade lägre gränser som visar att O (mn) är optimal upp till loggfaktorer. I SODA 2011 visade Bernstein och Roditty hur man kan kringgå dessa nedre gränser och förbättra på Even och Shiloach O (mn) total uppdateringstid som är bunden genom att tillåta en (1 + ) approximation. Detta utlöste en serie nya resultat, som kulminerade i ett nyligen genombrott av Henzinger, Krinninger och Nanongkai [FOCS 14], som presenterade en (1 + )-ungefärlig algoritm vars totala uppdateringstid är nära linjär: O(m 1 + O(1/ ε log n) ). Emellertid, var och en av dessa förbättringar över Even-Shiloach algoritmen randomiserades och antogs en icke-adaptiv motståndare. Detta ytterligare antagande innebar att algoritmerna inte var lämpliga för vissa inställningar och inte kunde användas som en svart låda datastruktur. Mycket nyligen Bernstein och Chechik presenteras i STOC 2016 den första deterministiska förbättringen över Even och Shiloach, som inte förlitade sig på randomisering eller antaganden om motståndaren: i en oriktad oviktad graf algoritmen upprätthåller (1+ )-ungefärliga avstånd och har total uppdateringstid Õ(n 2 ). I detta dokument presenterar vi en ny deterministisk algoritm för problemet med total uppdateringstid Õ(n 1,25 ε m) = O(mn 3/4 ): den returnerar en (1 + ) approximation, och är begränsad till oriktade oviktade grafer. Även om detta resultat fortfarande är långt ifrån att matcha den randomiserade nästan linjära totala uppdateringstiden, presenterar det viktiga framsteg mot den riktningen, eftersom till skillnad från STOC 2016 Õ(n 2 ) algoritm det slår Even och Shiloach O (mn) bundna för alla grafer, inte bara tillräckligt täta. I synnerhet var algoritmen Õ(n 2 ) helt beroende av en ny sparifieringsteknik, och kunde därför inte hoppas på att ge en förbättring för glesa grafer. Vi presenterar den första deterministiska förbättringen för glesa grafer
De presenterade också en algoritm för glesa grafer REF med uppdateringstid Õ(n 1,25 m) = Õ(mn 3/4 ).
Deterministic partially dynamic single source shortest paths for sparse graphs
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}