科研之友
微信
新浪微博
Facebook
分享链接
摘要
A fault-tolerant structure for a network is required for continued functioning following the failure of some of the network's edges or vertices. This article considers breadth-first search (BFS) spanning trees and addresses the problem of designing a sparse fault-tolerant BFS structure (FT-BFS structure), namely, a sparse subgraph T of the given network G such that subsequent to the failure of a single edge or vertex, the surviving part T' of T still contains a BFS spanning tree for (the surviving part of) G. For a source node s, a target node t, and an edge e epsilon G, the shortest s - t path P-s,P-t,P-e that does not go through e is known as a replacement path. Thus, our FT-BFS structure contains the collection of all replacement paths P-s,P-t,P-e for every t epsilon V(G) and every failed edge e epsilon E(G). Our main results are as follows. We present an algorithm that for every n-vertex graph G and source node s constructs a (single edge failure) FT-BFS structure rooted at s with O(n center dot min{Depth(s),root n}) edges, where Depth(s) is the depth of the BFS tree rooted at s. This result is complemented by a matching lower bound, showing that there exist n-vertex graphs with a source node s for which any edge (or vertex) FT-BFS structure rooted at s has Omega(n(3/2)) edges. We then consider fault-tolerant multi-source BFS structures (FT-MBFS structures), aiming to provide (following a failure) a BFS tree rooted at each source s(i) epsilon S for some subset of sources S subset of V. Again, tight bounds are provided, showing that there exists a poly-time algorithm that for every n-vertex graph and source set S subset of V of size s constructs a (single failure) FT-MBFS structure T*(S) from each source si. S, with O(root sigma center dot n(3/2)) edges, and, on the other hand, there exist n-vertex graphs with source sets S subset of V of cardinality sigma, on which any FT-MBFS structure from S has Omega(root sigma n(3/2)) edges. Finally, we propose an O(log n) approximation algorithm for constructing FT-BFS and FT-MBFS structures. The latter is complemented by a hardness result stating that there exists no Omega(log n) approximation algorithm for these problems under standard complexity assumptions. In comparison with previous constructions, our algorithm is deterministic and may improve the number of edges by a factor of up to root n for some instances. All our algorithms can be extended to deal with one vertex failure as well, with the same performance.
- 出版日期2016-12
