DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2021.43

Reliable Spanners for Metric Spaces

Authors: Sariel Har-Peled, Manor Mendel, and Dániel Oláh

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

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, that is, 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.

Cite as

Sariel Har-Peled, Manor Mendel, and Dániel Oláh. Reliable Spanners for Metric Spaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2021.43,
  author =	{Har-Peled, Sariel and Mendel, Manor and Ol\'{a}h, D\'{a}niel},
  title =	{{Reliable Spanners for Metric Spaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.43},
  URN =		{urn:nbn:de:0030-drops-138423},
  doi =		{10.4230/LIPIcs.SoCG.2021.43},
  annote =	{Keywords: Spanners, reliability}
}

Document

DOI: 10.4230/LIPIcs.ESA.2020.27

Sometimes Reliable Spanners of Almost Linear Size

Authors: Kevin Buchin, Sariel Har-Peled, and Dániel Oláh

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract

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.

Cite as

Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. Sometimes Reliable Spanners of Almost Linear Size. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2020.27,
  author =	{Buchin, Kevin and Har-Peled, Sariel and Ol\'{a}h, D\'{a}niel},
  title =	{{Sometimes Reliable Spanners of Almost Linear Size}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.27},
  URN =		{urn:nbn:de:0030-drops-128934},
  doi =		{10.4230/LIPIcs.ESA.2020.27},
  annote =	{Keywords: Geometric spanners, vertex failures, reliability}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2019.19

A Spanner for the Day After

Authors: Kevin Buchin, Sariel Har-Peled, and Dániel Oláh

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract

We show how to construct (1+epsilon)-spanner over a set P of n points in R^d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters theta, epsilon in (0,1), the computed spanner G has O(epsilon^{-7d} log^7 epsilon^{-1} * theta^{-6} n log n (log log n)^6) edges. Furthermore, for any k, and any deleted set B subseteq P of k points, the residual graph G \ B is (1+epsilon)-spanner for all the points of P except for (1+theta)k of them. No previous constructions, beyond the trivial clique with O(n^2) edges, were known such that only a tiny additional fraction (i.e., theta) lose their distance preserving connectivity. Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one dimensional construction in a black box fashion.

Cite as

Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. A Spanner for the Day After. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2019.19,
  author =	{Buchin, Kevin and Har-Peled, Sariel and Ol\'{a}h, D\'{a}niel},
  title =	{{A Spanner for the Day After}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.19},
  URN =		{urn:nbn:de:0030-drops-104237},
  doi =		{10.4230/LIPIcs.SoCG.2019.19},
  annote =	{Keywords: Geometric spanners, vertex failures, robustness}
}

Search Results

Documents authored by Oláh, Dániel

Reliable Spanners for Metric Spaces

Abstract

Cite as

Sometimes Reliable Spanners of Almost Linear Size

Abstract

Cite as

A Spanner for the Day After

Abstract

Cite as

Thanks for your feedback!

Could not send message