Sometimes reliable spanners of almost linear size

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 Ω(n log 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 Rd, are known, where the resulting graph has O(n log n loglog6n) 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 Rd with O(n loglog2n logloglog n) edges.

Original languageEnglish (US)
Title of host publication28th Annual European Symposium on Algorithms, ESA 2020
EditorsFabrizio Grandoni, Grzegorz Herman, Peter Sanders
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771627
DOIs
StatePublished - Aug 1 2020
Event28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italy
Duration: Sep 7 2020Sep 9 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume173
ISSN (Print)1868-8969

Conference

Conference28th Annual European Symposium on Algorithms, ESA 2020
Country/TerritoryItaly
CityVirtual, Pisa
Period9/7/209/9/20

Keywords

  • Geometric spanners
  • Reliability
  • Vertex failures

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Sometimes reliable spanners of almost linear size'. Together they form a unique fingerprint.

Cite this