In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of O(m n ). Here we provide the first deterministic algorithm for this problem, with the same O(m n ) time. For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a data-structure, such that given a query (s,t,F) with s,t V and F E V, |F| f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G F ( i.e. , the distance from s to t in the graph G after removing from it the failing edges and vertices F). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented a combinatorial randomized f-DSO with O(mn^ 4- ) preprocessing time and subquadratic O(n^ 2-2(1- ) f ) query time for every value of 0 < < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time.
@cite_41: This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new algorithm is extremely efficient as compared with the algorithms proposed by Bock, Kantner, and Haynes [2], Pollack [7], [8], Clarke, Krikorian, and Rausan [3], Sakarovitch [9] and others. This paper first reviews the algorithms presently available for finding the K shortest loopless paths in terms of the computational effort and memory addresses they require. This is followed by the presentation of the new algorithm and its justification. Finally, the efficiency of the new algorithm is examined and compared with that of other algorithms.
@cite_14: 
@cite_10: Let @math be any undirected graph on @math vertices and @math edges. A path @math between any two vertices @math is said to be @math -approximate shortest path if its length is at most @math times the length of the shortest path between @math and @math . We consider the problem of building a compact data structure for a given graph @math which is capable of answering the following query for any @math and @math . report @math -approximate shortest path between @math and @math when vertex @math fails We present data structures for the single source as well all-pairs versions of this problem. Our data structures guarantee optimal query time. Most impressive feature of our data structures is that their size nearly match the size of their best static counterparts.
The best known randomized algorithm for the @math simple shortest paths problem in directed unweighted graphs takes @math time ( @cite_10 ), leaving a significant gap compared to the best known deterministic algorithm which takes @math time ( e.g. , @cite_41 , @cite_14 ). We close this gap by proving the existence of a deterministic algorithm for computing @math simple shortest paths in unweighted directed graphs whose runtime is @math .