
For FullText 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 3EdgeConnect a Graph
Toshimasa WATANABE Mitsuhiro YAMAKADO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E76A
No.4
pp.518531 Publication Date: 1993/04/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: lineartime algorithms, 3edgeconnected graphs, connectivity augmentation, computational complexity,
Full Text: PDF(1.1MB)>>
Summary:
The subject of the paper is to propose an O(V+E) algorithm for the 3edgeconnectivity augmentation problem (UW3ECA) defined by "Given an undirected graph G_{0}=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G_{0}+E ) is 3edgeconnected, where each edge of E connects distinct vertices of V." Such a set E is called a solution to the problem. Let UW3ECA(S) (UW3ECA(M), respectively) denote UW3ECA in which G_{0}+E is required to be simple (G_{0}+E may have multiple edges). Note that we can assume that G_{0} is simple in UW3ECA(S). UW3ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all kedgeconnected components of a given graph for every k3, and (2) determining a minimum set of edges whose addition to G_{0} result in a 3edgeconnected 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 UW3ECA(M). Furthermore, it is shown that a solution E to UW3ECA(M) is also a solution to UW3ECA(S) if V4, partly solving an open problem UWkECA(S) that is a generalization of UW3ECA(S).

