TY - JOUR

T1 - SOMETIMES RELIABLE SPANNERS OF ALMOST LINEAR SIZE

AU - Buchin, Kevin

AU - Har-Peled, Sariel

AU - Oláh, Dániel

N1 - Funding Information:
∗Sariel Har-Peled was partially supported by NSF AF awards CCF-1421231 and CCF-1907400. Dániel Oláh was supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. A preliminary version of this paper appeared in ESA 2020 [5].
Publisher Copyright:
© 2022, Carleton University. All rights reserved.

PY - 2022

Y1 - 2022

N2 - Reliable (Euclidean) 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 Euclidean 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.

AB - Reliable (Euclidean) 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 Euclidean 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.

UR - http://www.scopus.com/inward/record.url?scp=85129220427&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85129220427&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85129220427

SN - 1920-180X

VL - 13

SP - 178

EP - 196

JO - Journal of Computational Geometry

JF - Journal of Computational Geometry

IS - 1

ER -