Reliable spanners for metric spaces

Sariel Har-Peled, Manor Mendel, 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, 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.

שפה מקוריתאנגלית
כותר פרסום המארח37th International Symposium on Computational Geometry, SoCG 2021
עורכיםKevin Buchin, Eric Colin de Verdiere
מוציא לאורSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
מסת"ב (אלקטרוני)9783959771849
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יוני 2021
אירוע37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, ארצות הברית
משך הזמן: 7 יוני 202111 יוני 2021

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך189
ISSN (מודפס)1868-8969

כנס

כנס37th International Symposium on Computational Geometry, SoCG 2021
מדינה/אזורארצות הברית
עירVirtual, Buffalo
תקופה7/06/2111/06/21

הערה ביבליוגרפית

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).

פורמט ציטוט ביבליוגרפי