2026-07-23T18:19:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12893 2024-03-06T10:51:01Z ddc:004 open_access

Sometimes Reliable Spanners of Almost Linear Size Buchin, Kevin Har-Peled, Sariel Oláh, Dániel Geometric spanners vertex failures reliability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Buchin and Sariel Har-Peled and Dániel Oláh 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.27 urn:nbn:de:0030-drops-128934 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.27 eng https://creativecommons.org/licenses/by/3.0/legalcode