Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


Let G = (V, E) be a directed edge-weighted graph and let P be a shortest path from s to t in G. The {em replacement paths} problem asks to compute, for every edge e on P, the shortest s-to-t path that avoids e. Apart from approximation algorithms and algorithms for special graph classes, the naive solution to this problem -- removing each edge e on P one at a time and computing the shortest s-to-t path each time -- is surprisingly the only known solution for directed weighted graphs, even when the weights are integrals. In particular, although the related {em shortest paths} problem has benefited from fast matrix multiplication, the replacement paths problem has not, and still required cubic time. For an n-vertex graph with integral edge-lengths in {-M,...,M}, we give a randomized O(Mn^{1+2omega/3}) = O(Mn^{2.584}) time algorithm that uses fast matrix multiplication and is sub-cubic for appropriate values of M. In particular, it runs in O(n^{1+2omega/3}) time if the weights are small (positive or negative) integers. We also show how to construct a distance sensitivity oracle in the same time bounds. A query (u,v,e) to this oracle requires sub-quadratic time and returns the length of the shortest u-to-v path that avoids the edge e. In fact, for any constant number of edge failures, we construct a data structure in sub-cubic time, that answer queries in sub-quadratic time. Our results also apply for avoiding vertices rather than edges.

Questions and Answers

You need to be logged in to be able to post here.