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_33: Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn+n^2logn)). For the replacement paths problem the best known result is the trivial one running in time O(mn+n^2logn). In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn+n^2loglogn). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n^2loglogn) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs. Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs.
@cite_8: A naive algorithm for the replacement paths problem runs in O(n(m+n logn)) time, executing the single-source shortest path algorithm up to n times. In our paper [3], we claimed that the replacement paths problem can be solved inO(m+n logn) time for both undirected and directed graphs. However, there is a flaw that invalidates the algorithm for directed graphs. (The algorithm for undirected graphs remains valid.) The same bound for undirected graphs is also achieved by Nardelli, Proietti, and Widmayer [6], who solve the most vital node problem with an algorithm that also solves the replacement paths problem. Their work is in turn based on earlier work by Malik, Mittal and Gupta [5], Ball, Golden, and Vohra [1] and BarNoy, Khuller, and Schieber [2]. The error in our algorithm for directed graphs led us to investigate the hardness of the replacement paths problem and other related problems. We have recently established lower bounds that show that no replacement paths algorithm of a certain class (including all known algorithms) can achieve the running time of the algorithm for undirected graphs [4]. The mistake in the directed graph algorithm of [3] occurs on page 257, just after Lemma 2, where we say “A simple corollary of this lemma is the fact that if (u; v) is the single edge of path(x; y; G n e) in E(Vx; Vy), then
@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.
@cite_21: Let G = (V, E) be a directed graph with positive edge weights, let s, t be two specified vertices in this graph, and let π(s, t) be the shortest path between them. In the replacement paths problem we want to compute, for every edge e on π(s, t), the shortest path from s to t that avoids e. The naive solution to this problem would be to remove each edge e, one at a time, and compute the shortest s - t path each time; this yields a running time of O(mn + n2 log n). Gotthilf and Lewenstein [8] recently improved this to O(mn+n2 log log n), but no o(mn) algorithms are known. We present the first approximation algorithm for replacement paths in directed graphs with positive edge weights. Given any e e [0, 1), our algorithm returns (1 + e)-approximate replacement paths in O(e-1 log2 n log(nC c)(m+n log n)) = O(m log(nC c) e) time, where C is the largest edge weight in the graph and c is the smallest weight. We also present an even faster (1 + e) approximate algorithm for the simpler problem of approximating the k shortest simple s - t paths in a directed graph with positive edge weights. That is, our algorithm outputs k different simple s - t paths, where the kth path we output is a (1 + e) approximation to the actual kth shortest simple s - t path. The running time of our algorithm is O(ke-1 log2 n(m + n log n)) = O(km e). The fastest exact algorithm for this problem has a running time of O(k(mn+n2 log log n)) = O(kmn) [8]. The previous best approximation algorithm was developed by Roditty [15]; it has a stretch of 3 2 and a running time of O(km√n) (it does not work for replacement paths). Note that all of our running times are nearly optimal except for the O (log(nC c)) factor in the replacements paths algorithm. Also, our algorithm can solve the variant of approximate replacement paths where we avoid vertices instead of edges.
@cite_6: The k most vital arcs in a network are those whose removal from the network results in the greatest increase in the shortest distance between two specified nodes. An exact algorithm is proposed to determine the k most vital arcs. Furthermore, an algorithm of time complexity equal to that of Dijkstra's algorithm for the shortest path problem is developed to solve the single most vital arc problem.
@cite_39: Let G = (V(G), E(G)) be a weighted directed graph and let P be a shortest path from s to t in G. In the replacement paths problem we are required to compute for every edge e in P, the length of a shortest path from s to t that avoids e. The fastest known algorithm for solving the problem in weighted directed graphs is the trivial one: each edge in P is removed from the graph in its turn and the distance from s to t in the modified graph is computed. The running time of this algorithm is O (mn + n2 log n), where n = |V(G)| and m = |E(G)|. The replacement paths problem is strongly motivated by two different applications. First, the fastest algorithm to compute the k simple shortest paths from s to t in directed graphs [21, 13] repeatedly computes the replacement paths from s to t. Its running time is O(kn(m + n log n)). Second, the computation of Vickrey pricing of edges in distributed networks can be reduced to the replacement paths problem. An open question raised by Nisan and Ronen [16] asks whether it is possible to compute the Vickrey pricing faster than the trivial algorithm described in the previous paragraph. In this paper we present a near-linear time algorithm for computing replacement paths in weighted planar directed graphs. In particular, the algorithm computes the lengths of the replacement paths in O(n log3 n) time. This result immediately improves the running time of the two applications mentioned above by almost a linear factor. Our algorithm is obtained by combining several new ideas with a data structure of Klein [12] that supports multi-source shortest paths queries in planar directed graphs in logarithmic time. Our algorithm can be adapted to address the variant of the problem in which one is interested in the replacement path itself (rather than the length of the path). In that case the algorithm is executed in a preprocessing stage constructing a data structure that supports replacement path queries in time O(h), where h is the number of hops in the replacement path. In addition, we can handle the variant in which vertices should be avoided instead of edges.
@cite_45: 
@cite_46: Abstract Let P G (r,s) denote a shortest path between two nodes r and s in an undirected graph G=(V,E) such that |V|=n and |E|=m and with a positive real length w(e) associated with any e∈E . In this paper we focus on the problem of finding an edge e ∗ ∈P G (r,s) whose removal is such that the length of P G−e ∗ (r,s) is maximum, where G−e ∗ =(V,E⧹ e ∗ ) . Such an edge is known as the most vital edge of the path P G (r,s) . We will show that this problem can be solved in O (m·α(m,n)) time, where α is the functional inverse of the Ackermann function, thus improving on the previous O (m+n log n) time bound.
@cite_13: We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to send data between two nodes along a shortest path? If the network is a decentralized entity, such as the Internet, in which multiple self-interested agents own different parts of the network, then auction-based pricing seems appropriate. A celebrated result from auction theory shows that the use of Vickrey pricing motivates the owners of the network resources to bid truthfully. In Vickrey's scheme, each agent is compensated in proportion to the marginal utility he brings to the auction. In the context of shortest path routing, an edge's utility is the value by which it lowers the length of the shortest path, i.e., the difference between the shortest path lengths with and without the edge. Our problem is to compute these marginal values for all the edges of the network efficiently. The naive method requires solving the single-source shortest path problem up to n times, for an n-node network. We show that the Vickrey prices for all the edges can be computed in the same asymptotic time complexity as one single-source shortest path problem. This solves an open problem posed by N. Nisan and A. Ronen (1999).
@cite_20: 
The replacement paths problem. The replacement paths problem is motivated by several different applications and has been extensively studied in the last few decades (see e.g. @cite_6 @cite_13 @cite_8 @cite_46 @cite_45 @cite_33 @cite_10 @cite_39 @cite_20 @cite_21 ). It is well motivated by its own right from the fault-tolerance perspective. In many applications it is desired to find algorithms and data-structures that are resilient to failures. Since links in a network can fail, it is important to find backup shortest paths between important vertices of the graph.