Home Bookmarks Papers Blog

# Sometimes Reliable Spanners of Almost Linear Size $\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\Of}{{\mathcal{O}}}% \newcommand{\distY}{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\epsR}{\vartheta}% \newcommand{\pts}{s}$

Kevin Buchin, Sariel Har-Peled, and Dániel Oláh.
PDF : ESA talk. : arxiv : DBLP.
Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, a reliable spanner may have some additional vertices for which the spanner property no longer holds, but this collateral damage is bounded by a fraction of the size of the attack. It is known that $\Omega(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+\eps)$-spanners, for $n$ points in $\Re^d$, are known, where the resulting graph has $O( n \log n \log \log^{6}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 $\Re^d$ with $O( n \log \log^{2} n \log \log \log n )$ edges.

PDF.