Document Open Access Logo

Roundtrip Spanners with (2k-1) Stretch

Authors Ruoxu Cen, Ran Duan, Yong Gu

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2020.24.pdf
  • Filesize: 487 kB
  • 11 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Graph theory
  • Deterministic algorithm
  • Roundtrip spanners

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Ruoxu Cen, Ran Duan, and Yong Gu. Roundtrip Spanners with (2k-1) Stretch. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 24:1-24:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.24

Author Details

Ruoxu Cen
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Ran Duan
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Yong Gu
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

References

  1. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167-1181, 1999. Google Scholar
  2. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81-100, January 1993. URL: https://doi.org/10.1007/BF02189308.
  3. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Improved approximation for the directed spanner problem. In International Colloquium on Automata, Languages, and Programming, pages 1-12, Berlin, Heidelberg, 2011. Springer. Google Scholar
  4. Piotr Berman, Sofya Raskhodnikova, and Ge Ruan. Finding sparser directed spanners. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 424-435, Dagstuhl, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.424.
  5. A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova, and D. Woodruff. Transitive-closure spanners. SIAM Journal on Computing, 41(6):1380-1425, 2012. URL: https://doi.org/10.1137/110826655.
  6. Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford. Improved Girth Approximation and Roundtrip Spanners. arXiv e-prints, page arXiv:1907.10779, July 2019. URL: http://arxiv.org/abs/1907.10779.
  7. Lenore J Cowen and Christopher G Wagner. Compact roundtrip routing for digraphs. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 885-886, Philadelphia, 1999. SIAM. Google Scholar
  8. Lenore J Cowen and Christopher G Wagner. Compact roundtrip routing in directed networks. In Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, pages 51-59, New York, 2000. ACM. Google Scholar
  9. Michael Dinitz and Robert Krauthgamer. Directed spanners via flow-based linear programs. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 323-332, New York, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993680.
  10. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000. Google Scholar
  11. Paul Erdös. Extremal problems in graph theory. In Theory of Graphs and Its Applications (Proc. Sympos. Smolenice, 1963), pages 29-36, Prague, 1964. Publ. House Czechoslovak Acad. Sci. Google Scholar
  12. Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, 1987. Google Scholar
  13. Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, and Virginia Vassilevska Williams. Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1374-1392, Philadelphia, 2018. SIAM. Google Scholar
  14. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA, 2000. Google Scholar
  15. Sofya Raskhodnikova. Transitive-closure spanners: A survey. In Property Testing, pages 167-196. Springer, Berlin, Heidelberg, 2010. Google Scholar
  16. Liam Roditty, Mikkel Thorup, and Uri Zwick. Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms, 4(3):29:1-29:17, July 2008. URL: https://doi.org/10.1145/1367064.1367069.
  17. Mikkel Thorup and Uri Zwick. Approximate distance oracles. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pages 183-192, New York, 2001. ACM. Google Scholar
  18. Chun Jiang Zhu and Kam-Yiu Lam. Deterministic improved round-trip spanners. Information Processing Letters, 129:57-60, 2018. Google Scholar
  19. Uri Zwick. Exact and approximate distances in graphs: a survey. In European Symposium on Algorithms, pages 33-48, Berlin, Heidelberg, 2001. Springer. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact