文章基本信息

标题：Sometimes Reliable Spanners of Almost Linear Size
本地全文：下载
作者：Kevin Buchin ; Sariel Har-Peled ; D{'a}niel Ol{'a}h 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：27:1-27:15
DOI：10.4230/LIPIcs.ESA.2020.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Geometric spanners; vertex failures; reliability