TY - GEN
T1 - Reliable spanners for metric spaces
AU - Har-Peled, Sariel
AU - Mendel, Manor
AU - Oláh, Dániel
N1 - Publisher Copyright:
© Sariel Har-Peled, Manor Mendel, and Dániel Oláh; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).
PY - 2021/6/1
Y1 - 2021/6/1
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, 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.
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, 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.
KW - Reliability
KW - Spanners
UR - http://www.scopus.com/inward/record.url?scp=85108210323&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85108210323&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2021.43
DO - 10.4230/LIPIcs.SoCG.2021.43
M3 - Conference contribution
AN - SCOPUS:85108210323
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th International Symposium on Computational Geometry, SoCG 2021
A2 - Buchin, Kevin
A2 - de Verdiere, Eric Colin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th International Symposium on Computational Geometry, SoCG 2021
Y2 - 7 June 2021 through 11 June 2021
ER -