G0=(V,E), find an edge set E
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Linear Time Algorithm for Smallest Augmentation to 3-Edge-Connect a Graph
Toshimasa WATANABE Mitsuhiro YAMAKADO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E76-A No.4 pp.518-531
Publication Date: 1993/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
linear-time algorithms, 3-edge-connected graphs, connectivity augmentation, computational complexity,
Full Text: PDF(1.1MB)>>
The subject of the paper is to propose an O(|V|+|E|) algorithm for the 3-edge-connectivity augmentation problem (UW-3-ECA) defined by "Given an undirected graph G0=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G0+E ) is 3-edge-connected, where each edge of E connects distinct vertices of V." Such a set E is called a solution to the problem. Let UW-3-ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA in which G0+E is required to be simple (G0+E may have multiple edges). Note that we can assume that G0 is simple in UW-3-ECA(S). UW-3-ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all k-edge-connected components of a given graph for every k3, and (2) determining a minimum set of edges whose addition to G0 result in a 3-edge-connected graph. Concerning the subproblem (1), we use an O(|V|+|E|) algorithm that has already been existing. The paper proposes an O(|V|+|E|) algorithm for the subproblem (2). Combining these algorithms makes an O(|V|+|E|) algorithm for finding a solution to UW-3-ECA(M). Furthermore, it is shown that a solution E to UW-3-ECA(M) is also a solution to UW-3-ECA(S) if |V|4, partly solving an open problem UW-k-ECA(S) that is a generalization of UW-3-ECA(S).