Document Open Access Logo

Reliable Spanners for Metric Spaces

Authors Sariel Har-Peled , Manor Mendel , Dániel Oláh

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2021.43.pdf
  • Filesize: 0.78 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Spanners
  • reliability

Metrics

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

Abstract

A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation, that is, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees and (general) metric spaces.

Cite As Get BibTex

Sariel Har-Peled, Manor Mendel, and Dániel Oláh. Reliable Spanners for Metric Spaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.43

Author Details

Sariel Har-Peled
  • Department of Computer Science, University of Illinois, Urbana, IL USA
Manor Mendel
  • Department of Mathematics and Computer Science, The Open University of Israel, Raanana, Israel
Dániel Oláh
  • Department of Mathematics and Computing Science, TU Eindhoven, The Netherlands

Funding

  • Har-Peled, Sariel: Work on this paper was partially supported by a NSF AF award CCF-1907400.
  • Mendel, Manor: Supported by BSF Grant no. 2018223.
  • Oláh, Dániel: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

Acknowledgements

The authors thank Kevin Buchin for useful discussions and references.

References

  1. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. SIAM J. Comput., 48(3):1120-1145, 2019. URL: https://doi.org/10.1137/17M1112406.
  2. Y. Bartal. On approximating arbitrary metrics by tree metrics. In Proc. 30th Annu. ACM Sympos. Theory Comput. (STOC), pages 161-168, 1998. URL: https://doi.org/10.1145/276698.276725.
  3. Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric Ramsey-type phenomena. Ann. of Math. (2), 162(2):643-709, 2005. URL: https://doi.org/10.4007/annals.2005.162.643.
  4. Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. Optimal Vertex Fault Tolerant Spanners (for fixed stretch), pages 1884-1900. Society for Industrial and Applied Mathematics, 2018. URL: https://doi.org/10.1137/1.9781611975031.123.
  5. K. Buchin, S. Har-Peled, and D. Oláh. Sometimes reliable spanners of almost linear size. ArXiv, 2019. (accepted to ESA 2020). URL: http://arxiv.org/abs/1912.01547.
  6. K. Buchin, S. Har-Peled, and D. Oláh. A spanner for the day after. In Proceedings of the 35th Symposium on Computational Geometry, pages 19:1-19:15, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.19.
  7. T.-H. H. Chan, M. Li, L. Ning, and S. Solomon. New doubling spanners: Better and simpler. SIAM Journal on Computing, 44(1):37-53, 2015. URL: https://doi.org/10.1137/130930984.
  8. Ioana Dumitriu, Tobias Johnson, Soumik Pal, and Elliot Paquette. Functional limit theorems for random regular graphs. Probab. Theory Related Fields, 156(3-4):921-975, 2013. URL: https://doi.org/10.1007/s00440-012-0447-y.
  9. J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-497, 2004. URL: https://doi.org/10.1016/j.jcss.2004.04.011.
  10. Arnold Filtser and Hung Le. Reliable spanners: Locality-sensitive orderings strike back. CoRR, abs/2101.07428, 2021. URL: http://arxiv.org/abs/2101.07428.
  11. Sariel Har-Peled, Manor Mendel, and Dániel Oláh. Reliable spanners for metric spaces. CoRR, abs/2007.08738v2, 2021. URL: http://arxiv.org/abs/2007.08738v2.
  12. R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metric spaces. Geom. funct. anal. (GAFA), 15(4):839-858, 2005. Google Scholar
  13. C. Levcopoulos, G. Narasimhan, and M. Smid. Efficient algorithms for constructing fault-tolerant geometric spanners. In Proceedings of the 30th ACM Symposium on Theory of Computing, pages 186-195, 1998. URL: https://doi.org/10.1145/276698.276734.
  14. C. Levcopoulos, G. Narasimhan, and M. Smid. Improved algorithms for constructing fault-tolerant spanners. Algorithmica, 32(1):144-156, 2002. URL: https://doi.org/10.1007/s00453-001-0075-x.
  15. R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. URL: https://doi.org/10.1137/0136016.
  16. T. Lukovszki. New results of fault tolerant geometric spanners. In Proceedings of the 6th Workshop on Algorithms and Data Structures, pages 193-204, 1999. URL: https://doi.org/10.1007/3-540-48447-7_20.
  17. M. Mendel and A. Naor. Ramsey partitions and proximity data structures. J. Euro. Math. Soc., 009(2):253-275, 2007. URL: http://eudml.org/doc/277787.
  18. G. Narasimhan and M. Smid. Geometric spanner networks. Cambridge University Press, New York, NY, USA, 2007. Google Scholar
  19. D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. URL: https://doi.org/10.1137/1.9780898719772.
  20. D. Peleg and A. Schäffer. Graph spanners. J. Graph Theory, 13:99-116, 1989. Google Scholar
  21. S. Solomon. From hierarchical partitions to hierarchical covers: Optimal fault-tolerant spanners for doubling metrics. In Proceedings of the 46th ACM Symposium on Theory of Computing, STOC ’14, page 363–372, 2014. URL: https://doi.org/10.1145/2591796.2591864.
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