Fault Tolerant Approximate BFS Structures with Additive Stretch
- PDF / 1,119,610 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 39 Downloads / 152 Views
Fault Tolerant Approximate BFS Structures with Additive Stretch Merav Parter1 · David Peleg1 Received: 16 November 2017 / Accepted: 8 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper addresses the problem of designing a β-additive fault-tolerant approximate BFS (or FT-ABFS for short) structure, namely, a subgraph H of the network G such that subsequent to the failure of a single edge e, the surviving part of H still contains an approximate BFS spanning tree for (the surviving part of) G, whose distances satisfy dist(s, v, H \{e}) ≤ dist(s, v, G\{e}) + β for every v ∈ V . It was shown in Parter and Peleg (SODA, 2014), that for every β ∈ [1, O(log n)] there exists an nvertex graph G with a source s for which any β-additive FT-ABFS structure rooted at s has (n 1+(β) ) edges, for some function (β) ∈ (0, 1). In particular, 3-additive FT-ABFS structures admit a lower bound of (n 5/4 ) edges. In this paper we present the first upper bound, showing that there exists a poly-time algorithm that for every nvertex unweighted undirected graph G and source s constructs a 4-additive FT-ABFS structure rooted at s with at most O(n 4/3 ) edges. The main technical contribution of our algorithm is in adapting the path-buying strategy used in Baswana et al. (ACM Trans Algorithms 7:A5, 2010) and Cygan et al. (Proceedings of the 30th symposium on theoretical aspects of computer science, pp 209–220, 2013) to failure-prone settings. Keywords Replacement paths · Fault tolerance · Additive spanners Recipient of the Google European Fellowship in distributed computing; research is supported in part by this Fellowship. An extended abstract of this paper has appeared in the proceedings of the 2014 ACM-SIAM Symposium on Discrete Algorithms. Supported in part by the Israel Science Foundation (Grant 894/09), the United States-Israel Binational Science Foundation (Grant 2008348), the I-CORE program of the Israel PBC and ISF (Grant 4/11), the Israel Ministry of Science and Technology (infrastructures grant), and the Citi Foundation.
B
Merav Parter [email protected] David Peleg [email protected]
1
Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel
123
Algorithmica
1 Introduction Background and Motivation Fault-tolerant subgraphs are subgraphs designed to maintain a certain desirable property in the presence of edge or vertex failures. This paper focuses on the property of containing an additive approximate BFS structure resilient to the failure of a single edge in the graph. For an unweighted graph G = (V , E) and vertices v, w ∈ V , let dist(v, w, G) denote the distance (namely, the length of the shortest path) in edges between v and w. For a given source vertex s, a fault tolerant β-additive BFS structure resistant to a single edge failure is a subgraph H ⊆ G whose distances satisfy dist(s, v, H \{e}) ≤ dist(s, v, G\{e}) + β for every vertex v ∈ V and edge e ∈ E. The exact version of this question has recently bee
Data Loading...
