A Linear Time Algorithm for Smallest Augmentation to 3-Edge-Connect a Graph

Toshimasa WATANABE; Mitsuhiro YAMAKADO

A Linear Time Algorithm for Smallest Augmentation to 3-Edge-Connect a Graph

Toshimasa WATANABE, Mitsuhiro YAMAKADO

Full Text Views

0

Cite this

Summary :

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₀=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G₀+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 G₀+E is required to be simple (G₀+E may have multiple edges). Note that we can assume that G₀ 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 G₀ 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).

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.4 pp.518-531

Publication Date: 1993/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Toshimasa WATANABE, Mitsuhiro YAMAKADO, "A Linear Time Algorithm for Smallest Augmentation to 3-Edge-Connect a Graph" in IEICE TRANSACTIONS on Fundamentals, vol. E76-A, no. 4, pp. 518-531, April 1993, doi: .
Abstract: 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₀=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G₀+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 G₀+E is required to be simple (G₀+E may have multiple edges). Note that we can assume that G₀ 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 G₀ 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).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_4_518/_p

Copy

@ARTICLE{e76-a_4_518,
author={Toshimasa WATANABE, Mitsuhiro YAMAKADO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Linear Time Algorithm for Smallest Augmentation to 3-Edge-Connect a Graph},
year={1993},
volume={E76-A},
number={4},
pages={518-531},
abstract={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₀=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G₀+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 G₀+E is required to be simple (G₀+E may have multiple edges). Note that we can assume that G₀ 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 G₀ 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).},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - A Linear Time Algorithm for Smallest Augmentation to 3-Edge-Connect a Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 518
EP - 531
AU - Toshimasa WATANABE
AU - Mitsuhiro YAMAKADO
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1993
AB - 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₀=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G₀+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 G₀+E is required to be simple (G₀+E may have multiple edges). Note that we can assume that G₀ 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 G₀ 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).
ER -