Computing almost shortest paths
Michael Elkin · ACM Transactions on Algorithms · 2005
We study the s-sources almost shortest paths (abbreviated s-ASP) problem. Given an unweighted graph G = (V,E), and a subset S ⊆ V of s nodes, the goal is to compute almost shortest paths between all the pairs of nodes S × V. We devise an algorithm with running time O(∣E∣nρ + s · n1 + ζ) for this problem that computes the paths Pu,w for all pairs (u,w) ∈ S × V such that the length of Pu,w is at most (1 + ε) dG(u,w) + β(ζ,ρ,ε), and β(ζ,ρ,ε) is constant when ζ, ρ, and ε are arbitrarily small constants. We also devise a distributed protocol for the s-ASP problem that computes the paths Pu,w as above, and has time and communication complexities of O(s · Diam(G) + n1 + ζ/2) (respectively, O(s · Diam(G) log3 n + n1 + ζ/2 log n)) and O(∣E∣ nρ + s · n1 + ζ) (respectively, O(∣E∣ nρ + s · n1 + ζ + n1 + ρ + ζ(ρ − ζ/2)/2)) in the synchronous (respectively asynchronous) setting. Our sequential algorithm, as well as the distributed protocol, is based on a novel algorithm for constructing (1 + ε, β(ζ,ρ, ε))-spanners of size O(n1 + ζ), developed in this article. This algorithm has running time of O(∣E∣ nρ), which is significantly faster than the previously known algorithm given in Elkin and Peleg [2001], whose running time is Õ(n2 + ρ). We also develop the first distributed protocol for constructing (1 + ε,β)-spanners. The communication complexity of this protocol is near optimal.