Document Open Access Logo

Spanner Approximations in Practice

Authors Markus Chimani , Finn Stutzenstein

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.37.pdf
  • Filesize: 1.94 MB
  • 15 pages

Document Identifiers

Author Details

Markus Chimani
  • Theoretical Computer Science, Universität Osnabrück, Germany
Finn Stutzenstein
  • Theoretical Computer Science, Universität Osnabrück, Germany

Cite AsGet BibTex

Markus Chimani and Finn Stutzenstein. Spanner Approximations in Practice. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.37

Abstract

A multiplicative α-spanner H is a subgraph of G = (V,E) with the same vertices and fewer edges that preserves distances up to the factor α, i.e., d_H(u,v) ≤ α⋅ d_G(u,v) for all vertices u, v. While many algorithms have been developed to find good spanners in terms of approximation guarantees, no experimental studies comparing different approaches exist. We implemented a rich selection of those algorithms and evaluate them on a variety of instances regarding, e.g., their running time, sparseness, lightness, and effective stretch.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
  • General and reference → Experimentation
Keywords
  • Graph spanners
  • experimental study
  • algorithm engineering

Metrics

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

Related Versions

References

  1. Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence. Graph spanners: A tutorial review. Computer Science Review, 37:100253, 2020. URL: https://doi.org/10.1016/j.cosrev.2020.100253.
  2. Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, and Richard Spence. Approximation algorithms and an integer program for multi-level graph spanners. In Proc. SEA 2019, volume 11544 of LNCS, pages 541-562. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-34029-2.
  3. Stephen Alstrup, Sören Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen. Constructing light spanners deterministically in near-linear time. In Proc. ESA 2019, volume 144 of LIPIcs, pages 4:1-4:15. LZI Dagstuhl, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.4.
  4. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete Computational Geometry, 9:81-100, 1993. URL: https://doi.org/10.1007/BF02189308.
  5. Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804-823, 1985. URL: https://doi.org/10.1145/4221.4227.
  6. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms, 30(4):532-563, 2007. URL: https://doi.org/10.1002/rsa.20130.
  7. Benchmark and experimental data. Url. https://tcs.uos.de/research/spanner, 2022.
  8. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Approximation algorithms for spanner problems and directed Steiner forest. Information and Computation, 222:93-107, 2013. URL: https://doi.org/10.1016/j.ic.2012.10.007.
  9. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-closure spanners. In Proc. SODA 2009, pages 932-941. ACM SIAM, 2009. URL: https://doi.org/10.1137/110826655.
  10. Quirijn W. Bouts, Alex P. ten Brink, and Kevin Buchin. A framework for computing the greedy spanner. In Proc. SoCG 2014, pages 11-19. ACM, 2014. URL: https://doi.org/10.1145/2582112.2582154.
  11. Leizhen Cai. NP-completeness of minimum spanner problems. Discrete Applied Mathematics, 48(2):187-194, 1994. URL: https://doi.org/10.1016/0166-218X(94)90073-6.
  12. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67-90, 1995. URL: https://doi.org/10.1145/200836.200853.
  13. Barun Chandra, Gautam Das, Giri Narasimhan, and José Soares. New sparseness results on graph spanners. In Proc. SoCG 1992, pages 192-201. ACM, 1992. URL: https://doi.org/10.1145/142675.142717.
  14. Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. The open graph drawing framework (ogdf). In Roberto Tamassia, editor, Handbook of graph drawing and visualization, chapter 17. CRC press, 2014. Google Scholar
  15. Markus Chimani and Finn Stutzenstein. Spanner approximations in practice. arXiv, 2022. URL: http://arxiv.org/abs/2107.02018.
  16. Kenneth Lee Clarkson. Approximation algorithms for shortest path motion planning. In Proc. STOC 1987, pages 56-65. ACM, 1987. URL: https://doi.org/10.1145/28395.28402.
  17. Lenore J. Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38(1):170-183, 2001. URL: https://doi.org/10.1006/jagm.2000.1134.
  18. Lenore J. Cowen and Christopher G. Wagner. Compact roundtrip routing in directed networks. Journal of Algorithms, 50(1):79-95, 2004. URL: https://doi.org/10.1016/j.jalgor.2003.08.001.
  19. IBM ILOG Cplex. V12. 1: User’s manual for cplex. International Business Machines Corporation, 46(53):157, 2009. URL: https://www.ibm.com/analytics/cplex-optimizer.
  20. Michael Dinitz and Robert Krauthgamer. Directed spanners via flow-based linear programs. arXiv, 2010. URL: http://arxiv.org/abs/1011.3701.
  21. Michael Dinitz and Zeyu Zhang. Approximating low-stretch spanners. In Proc. SODA 2016, pages 821-840. ACM SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch59.
  22. Michael Elkin. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM Journal on Computing, 36(2):433-456, 2006. URL: https://doi.org/10.1137/S0097539704441058.
  23. Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms, 15(1), 2018. URL: https://doi.org/10.1145/3274651.
  24. Michael Elkin, Ofer Neiman, and Shay Solomon. Light spanners. SIAM Journal on Discrete Mathematics, 29(3):1312-1321, 2015. URL: https://doi.org/10.1137/140979538.
  25. Michael Elkin and David Peleg. Approximating k-spanner problems for k>2. Theoretical Computer Science, 337(1):249-277, 2005. URL: https://doi.org/10.1016/j.tcs.2004.11.022.
  26. Michael Elkin and Shay Solomon. Fast constructions of lightweight spanners for general graphs. ACM Transactions on Algorithms, 12(3), 2016. URL: https://doi.org/10.1145/2836167.
  27. Mohammad Farshi and Joachim Gudmundsson. Experimental study of geometric t-spanners. ACM Journal on Experimental Algorithmics, 14, 2010. URL: https://doi.org/10.1145/1498698.1564499.
  28. Giorgio Gallo, Michael D. Grigoriadis, and Robert E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18(1):30-55, 1989. URL: https://doi.org/10.1137/0218003.
  29. Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. URL: https://doi.org/10.1145/48014.61051.
  30. Andrew Vladislav Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, EECS Department, University of California, Berkeley, 1984. Google Scholar
  31. Madhav Jha and Sofya Raskhodnikova. Testing and reconstruction of Lipschitz functions with applications to data privacy. SIAM Journal on Computing, 42(2):700-731, 2013. URL: https://doi.org/10.1137/110840741.
  32. J. Mark Keil. Approximating the complete Euclidean graph. In Proc. SWAT 1988, volume 318 of LNCS, pages 208-213. Springer, 1988. Google Scholar
  33. Thorsten Koch, Alexander Martin, and Stefan Voß. SteinLib: An updated library on Steiner tree problems in graphs. Technical Report ZIB-Report 00-37, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2000. URL: http://steinlib.zib.de/steinlib.php.
  34. Guy Kortsarz and David Peleg. Generating sparse 2-spanners. Journal of Algorithms, 17(2):222-236, 1994. URL: https://doi.org/10.1006/jagm.1994.1032.
  35. Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved parallel algorithms for spanners and hopsets. In Proc. SPAA 2015, pages 192-201. ACM, 2015. URL: https://doi.org/10.1145/2755573.2755574.
  36. Gary L. Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proc. SPAA 2013, pages 196-203. ACM, 2013. URL: https://doi.org/10.1145/2486159.2486180.
  37. David Peleg. Proximity-preserving labeling schemes and their applications. In Proc. WG 1999, volume 1665 of LNCS, pages 30-41. Springer, 1999. Google Scholar
  38. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: https://doi.org/10.1002/jgt.3190130114.
  39. David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. In Proc. PODC 1987, pages 77-85. ACM, 1987. URL: https://doi.org/10.1145/41840.41847.
  40. David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510-530, 1989. URL: https://doi.org/10.1145/65950.65953.
  41. Gerhard Reinelt. Tsplib—a traveling salesman problem library. ORSA Journal on Computing, 3(4):376-384, 1991. URL: https://doi.org/10.1287/ijoc.3.4.376.
  42. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61:389-401, 2011. Google Scholar
  43. H. Shpungin and M. Segal. Near optimal multicriteria spanner constructions in wireless ad-hoc networks. In IEEE INFOCOM 2009, pages 163-171, 2009. URL: https://doi.org/10.1109/INFCOM.2009.5061918.
  44. Mikkel Sigurd and Martin Zachariasen. Construction of minimum-weight spanners. In Proc. ESA 2004, volume 3221 of LNCS, pages 797-808. Springer, 2004. Google Scholar
  45. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM, 52(1):1-24, 2005. URL: https://doi.org/10.1145/1044731.1044732.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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