$
\newcommand{\Re}{\mathbb{R}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\SetX}{\mathsf{X}}
\newcommand{\rad}{r}
\newcommand{\Mh}[1]{#1}
\newcommand{\query}{q}
\newcommand{\eps}{\varepsilon}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}}
\newcommand{\Polygon}{\mathsf{P}}
\newcommand{\IntRange}[1]{[ #1 ]}
\newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\pt}{p}
\newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|}
\newcommand{\ptq}{q}
\newcommand{\pts}{s}$
Sariel Har-Peled,
Manor Mendel,
and
Dániel Oláh.
A spanner is reliable if it can withstand large, catastrophic
failures in the network. More precisely, any failure of some nodes
can only cause a small damage in the remaining graph in terms of
the dilation. Namely, the spanner property is maintained for
almost all nodes in the residual graph. Constructions of reliable
spanners of near linear size are known in the low-dimensional
Euclidean settings. Here, we present new constructions of reliable
spanners for planar graphs, trees and (general) metric spaces.
PDF.
:
arXiv
:
DBLP (SoCG).
Last modified: Sat 2022-07-23 20:41:03 UTC 2022 by Sariel Har-Peled