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. 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.
שפה מקוריתאנגלית אמריקאית
מספר המאמר1
עמודים (מ-עד)7:1-7:27
מספר עמודים27
כתב עתACM Trans. Algorithms
כרך19
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2023

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

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

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