Deterministic improved round-trip spanners

摘要

AbstractIn this paper, we study the deterministic construction of round-trip spanners for weighted directed graphs. We propose a deterministic algorithm which constructs, for anyn-vertex graphG(V,E), a round-trip spannerH(V,E′⊆E)of stretch2k+ϵand sizeO((k/ϵ)⋅n1+1/klog⁡(nw)), wherewis the maximum edge weight ofG. Notably, this is the first deterministic construction of round-trip spanners and its stretch-size trade-off even improves the previous state-of-the-art randomized algorithm by Roditty et al. More specifically, the size is asymptotically reduced by a factor ofkwhile the stretch factor remains the same. The result is the first clear improvement on round-trip spanners after about ten years and re-raises the open question that how best we can hope for the stretch-size trade-off of round-trip spanners in digraphs.Highlights•We study the first deterministic algorithm for constructing round-trip spanners.•Our deterministic algorithm out-performs the state-of-the-art randomized algorithm.•We re-raise the question that how best we can hope for the stretch-size trade-off.