A Linear Time Algorithm for Smallest Augmentation to 3Edge-Connect a Graph (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
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 G_0=(V,E), find an edge set E' of minimum cardinality such that the graph (V,E⋃E') (denoted as G_0+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-3ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA 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 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 k≦3, and (2) determining a minimum set of edges whose addition to G_0 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).
社団法人電子情報通信学会の論文
1993-04-25