A Fast Algorithm for Source-Wise Round-Trip Spanners
share
In this paper, we study the problem of efficiently constructing source-wise round-trip spanners in weighted directed graphs. For a source vertex set S⊆ V in a digraph G(V,E), an S-source-wise round-trip spanner of G of stretch k is a subgraph H of G such that for every u∈ S,v∈ V, the round-trip distance between u and v in H is at most k times of the original distance in G. We show that, for a digraph G(V,E) with n vertices, m edges and nonnegative edge weights, an s-sized source vertex set S⊆ V and a positive integer k, there exists an algorithm, in time O(ms^1/klog^5n), with high probability constructing an S-source-wise round-trip spanner of stretch O(klog n) and size O(ns^1/klog^2n). Compared with the state of the art for constructing source-wise round-trip spanners, our algorithm significantly improves their construction time Ω(min{ms,n^ω}) (where ω∈ [2,2.373) and 2.373 is the matrix multiplication exponent) to nearly linear O(ms^1/klog^5n), while still keeping a spanner stretch O(klog n) and size O(ns^1/klog^2n), asymptotically similar to their stretch 2k+ϵ and size O((k^2/ϵ)ns^1/klog(nw)), respectively.
READ FULL TEXT