Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
Surender Baswana, Telikepalli Kavitha · SIAM Journal on Computing · 2010
Let $G=(V,E)$ be a weighted undirected graph having nonnegative edge weights. An estimate $\hat{\delta}(u,v)$ of the actual distance $\delta(u,v)$ between $u,v\in V$ is said to be of stretch t if and only if $\delta(u,v)\leq\hat{\delta}(u,v)\leq t\cdot\delta(u,v)$. Computing all-pairs small stretch distances efficiently (both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1–24].