TY - JOUR
T1 - Reliable Spanners for Metric Spaces
AU - Har-Peled, Sariel
AU - Mendel, Manor
AU - Oláh, Dániel
N1 - Publisher Copyright:
© 2023 Association for Computing Machinery.
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 - http://www.scopus.com/inward/record.url?scp=85168622655&partnerID=8YFLogxK
U2 - 10.1145/3563356
DO - 10.1145/3563356
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:85168622655
SN - 1549-6325
VL - 19
SP - 7:1-7:27
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 1
M1 - 7
ER -