Reliable Spanners for Metric Spaces

Sariel Har-Peled; Manor Mendel; Dániel Oláh

doi:10.1145/3563356

Reliable Spanners for Metric Spaces

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

Siebel School of Computing and Data Science

Research output: Contribution to journal › Article › peer-review

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. In other words, 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.

Original language	English (US)
Article number	7
Journal	ACM Transactions on Algorithms
Volume	19
Issue number	1
Early online date	Mar 9 2023
DOIs	https://doi.org/10.1145/3563356
State	Published - Mar 9 2023

Keywords

Additional Key Words and PhrasesComputational geometry
reliable
spanners

ASJC Scopus subject areas

Mathematics (miscellaneous)

Online availability

10.1145/3563356

Library availability

Discover UIUC Full Text

Cite this

@article{be5eaa38f30b41edbd317f64e8fcc6fb,

title = "Reliable Spanners for Metric Spaces",

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. In other words, 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.",

keywords = "Additional Key Words and PhrasesComputational geometry, reliable, spanners",

author = "Sariel Har-Peled and Manor Mendel and D{\'a}niel Ol{\'a}h",

note = "S. Har-Peled work on this article was partially supported by NSF AF Award No. CCF-1907400. M. Mendel was supported by BSF Grant No. 2018223. D. Olah was supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation Grant NETWORKS No. 024.002.003.",

year = "2023",

month = mar,

day = "9",

doi = "10.1145/3563356",

language = "English (US)",

volume = "19",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery",

number = "1",

}

TY - JOUR

T1 - Reliable Spanners for Metric Spaces

AU - Har-Peled, Sariel

AU - Mendel, Manor

AU - Oláh, Dániel

N1 - S. Har-Peled work on this article was partially supported by NSF AF Award No. CCF-1907400. M. Mendel was supported by BSF Grant No. 2018223. D. Olah was supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation Grant NETWORKS No. 024.002.003.

PY - 2023/3/9

Y1 - 2023/3/9

N2 - 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. In other words, 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.

AB - 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. In other words, 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.

KW - Additional Key Words and PhrasesComputational geometry

KW - reliable

KW - spanners

UR - https://www.scopus.com/pages/publications/85168622655

UR - https://www.scopus.com/pages/publications/85168622655#tab=citedBy

U2 - 10.1145/3563356

DO - 10.1145/3563356

M3 - Article

AN - SCOPUS:85168622655

SN - 1549-6325

VL - 19

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 7

ER -

Reliable Spanners for Metric Spaces

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this