Sometimes Reliable Spanners of Almost Linear Size

Authors Kevin Buchin, Sariel Har-Peled, Dániel Oláh



PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.27.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Kevin Buchin
  • Department of Mathematics and Computing Science, TU Eindhoven, The Netherlands
Sariel Har-Peled
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA
Dániel Oláh
  • Department of Mathematics and Computing Science, TU Eindhoven, The Netherlands

Cite AsGet BibTex

Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. Sometimes Reliable Spanners of Almost Linear Size. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.27

Abstract

Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, some of the remaining vertices of a reliable spanner may no longer admit the spanner property, but this collateral damage is bounded by a fraction of the size of the attack. It is known that Ω(nlog n) edges are needed to achieve this strong property, where n is the number of vertices in the network, even in one dimension. Constructions of reliable geometric (1+ε)-spanners, for n points in ℝ^d, are known, where the resulting graph has 𝒪(n log n log log⁶n) edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical - replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip list like construction. This results in a 1-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in ℝ^d with 𝒪(n log log²n log log log n) edges.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Geometric spanners
  • vertex failures
  • reliability

Metrics

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

References

  1. J. Aspnes and G. Shah. Skip graphs. ACM Transactions on Algorithms, 3(4):37, November 2007. Google Scholar
  2. P. Bose, P. Carmi, V. Dujmović, and P. Morin. Near-optimal O(k)-robust geometric spanners. CoRR, abs/1812.09913, 2018. URL: http://arxiv.org/abs/1812.09913.
  3. P. Bose, V. Dujmović, P. Morin, and M. Smid. Robust geometric spanners. SIAM Journal on Computing, 42(4):1720-1736, 2013. URL: https://doi.org/10.1137/120874473.
  4. K. Buchin, S. Har-Peled, and D. Oláh. A spanner for the day after. In Proc. 35th Int. Annu. Sympos. Comput. Geom. (SoCG), pages 19:1-19:15, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.19.
  5. 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.
  6. T. M. Chan, S. Har-Peled, and M. Jones. On Locality-Sensitive Orderings and Their Applications. In Proc. 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), pages 21:1-21:17, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.21.
  7. C. Levcopoulos, G. Narasimhan, and M. Smid. Efficient algorithms for constructing fault-tolerant geometric spanners. In Proc. 30th Annu. ACM Sympos. Theory Comput. (STOC), pages 186-195, 1998. URL: https://doi.org/10.1145/276698.276734.
  8. 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.
  9. T. Lukovszki. New results of fault tolerant geometric spanners. In Proc. 6th Workshop Algorithms Data Struct. (WADS), pages 193-204, 1999. URL: https://doi.org/10.1007/3-540-48447-7_20.
  10. S. Solomon. From hierarchical partitions to hierarchical covers: Optimal fault-tolerant spanners for doubling metrics. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 363–372, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2591796.2591864.
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