文章基本信息
- 标题：New Fault Tolerant Subset Preservers
- 本地全文：下载
- 作者：Greg Bodwin ; Keerti Choudhary ; Merav Parter 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：168
- 页码：15:1-15:19
- DOI：10.4230/LIPIcs.ICALP.2020.15
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：Fault tolerant distance preservers are sparse subgraphs that preserve distances between given pairs of nodes under edge or vertex failures. In this paper, we present the first non-trivial constructions of subset distance preservers, which preserve all distances among a subset of nodes S, that can handle either an edge or a vertex fault. - For an n-vertex undirected weighted graph or weighted DAG G = (V,E) and S âS V, we present a construction of a subset preserver with OÌf( S n) edges that is resilient to a single fault. In the single pair case ( S = 2), the bound improves to O(n). We further provide a nearly-matching lower bound of Ω( S n) in either setting, and we show that the same lower bound holds conditionally even if attention is restricted to unweighted graphs. - For an n-vertex directed unweighted graph G = (V,E) and r â^^ V, S âS V, we present a construction of a preserver of distances in {r} Ã- S with OÌf(n^{4/3} S ^{5/6}) edges that is resilient to a single fault. In the case S = 1 the bound improves to O(n^{4/3}), and for this case we provide another matching conditional lower bound. - For an n-vertex directed weighted graph G = (V, E) and r â^^ V, S âS V, we present a construction of a preserver of distances in {r} Ã- S with OÌf(n^{3/2} S ^{3/4}) edges that is resilient to a single vertex fault. (It was proved in [Greg Bodwin et al., 2017] that the bound improves to O(n^{3/2}) when S = 1, and that this is conditionally tight.)
- 关键词：Subset Preservers; Distances; Fault-tolerance
