Vi presenterar ett förbättrat orakel för problemet med avståndskänslighet. Målet är att förbehandla en riktad graf G = (V, E) med icke-negativa kantvikter för att svara på frågor om formen: vad är längden på den kortaste vägen från x till y som inte går igenom någon misslyckad vertex eller kant f. Den tidigare bästa algoritmen producerar en orakel av storlek O(n 2 ) som har en O(1) frågetid, och en O(n 2 ε m) konstruktionstid. Det var en randomiserad Monte Carlo-algoritm som fungerade med stor sannolikhet. Vårt orakel har också en konstant frågetid och ett O(n 2 ) utrymmeskrav, men det har en förbättrad byggtid av O (mn), och det är deterministisk. Observera att O(1) fråga, O(n 2 ) utrymme, och O(mn) byggtid är också den mest kända bunden (upp till logaritmiska faktorer) för det enklare problemet att hitta alla par kortaste vägar i en viktad, riktad graf. Därför är vårt oraklet optimalt upp till logaritmiska faktorer, utan att förbättra lösningarna på alla parens kortaste vägproblem.
Konstruktion av O(n 2 )-utrymme och O(1)-query tid oracle är känd för single edge fel på grund av REF.
A nearly optimal oracle for avoiding failed vertices and edges
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}