Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.24
URN: urn:nbn:de:0030-drops-124313
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12431/
Cen, Ruoxu ; Duan, Ran ; Gu, Yong
Roundtrip Spanners with (2k-1) Stretch
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{cen_et_al:LIPIcs:2020:12431,
author = {Ruoxu Cen and Ran Duan and Yong Gu},
title = {{Roundtrip Spanners with (2k-1) Stretch}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {24:1--24:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12431},
URN = {urn:nbn:de:0030-drops-124313},
doi = {10.4230/LIPIcs.ICALP.2020.24},
annote = {Keywords: Graph theory, Deterministic algorithm, Roundtrip spanners}
}
| Keywords: | Graph theory, Deterministic algorithm, Roundtrip spanners | |
| Seminar: | 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 29.06.2020 |
