Near Optimal Algorithms For The Single Source Replacement Paths Problem
Shiri Chechik, Sarel Cohen · Society for Industrial and Applied Mathematics eBooks · 2019
The Single Source Replacement Paths (SSRP) problem is as follows; Given a graph G = (V, E), a source vertex s and a shortest paths tree Ts rooted in s, output for every vertex t ∊ V and for every edge e in Ts the length of the shortest path from s to t avoiding e. We present near optimal upper bounds, by providing time randomized combinatorial algorithm 1 for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.