2026-07-25T03:00:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12431 2024-03-06T10:50:07Z ddc:004 open_access

Roundtrip Spanners with (2k-1) Stretch Cen, Ruoxu Duan, Ran Gu, Yong Graph theory Deterministic algorithm Roundtrip spanners A roundtrip spanner of a directed graph G is a subgraph of G preserving roundtrip distances approximately for all pairs of vertices. Despite extensive research, there is still a small stretch gap between roundtrip spanners in directed graphs and undirected graphs. For a directed graph with real edge weights in [1,W], we first propose a new deterministic algorithm that constructs a roundtrip spanner with (2k-1) stretch and O(k n^(1+1/k) log (nW)) edges for every integer k > 1, then remove the dependence of size on W to give a roundtrip spanner with (2k-1) stretch and O(k n^(1+1/k) log n) edges. While keeping the edge size small, our result improves the previous 2k+ε stretch roundtrip spanners in directed graphs [Roditty, Thorup, Zwick'02; Zhu, Lam'18], and almost matches the undirected (2k-1)-spanner with O(n^(1+1/k)) edges [Althöfer et al. '93] when k is a constant, which is optimal under Erdös conjecture. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ruoxu Cen and Ran Duan and Yong Gu 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.24 urn:nbn:de:0030-drops-124313 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.24 eng https://creativecommons.org/licenses/by/3.0/legalcode