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_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_34: 
@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_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.
The replacement paths problem has been studied extensively, and by now near optimal algorithms are known for many cases of the problem. For instance, the case of undirected graphs admits deterministic near linear solutions (see @cite_6 @cite_13 @cite_34 @cite_46 ). In fact, Lee and Lu present linear @math -time algorithms for the replacement-paths problem in on the following classes of @math -node @math -edge graphs: (1) undirected graphs in the word-RAM model of computation, (2) undirected planar graphs, (3) undirected minor-closed graphs, and (4) directed acyclic graphs.