A Linear-Time Algorithm for Computing All 3-Edge-Connected Components of a Multigraph

Satoshi TAOKA; Toshimasa WATANABE; Kenji ONAGA

A Linear-Time Algorithm for Computing All 3-Edge-Connected Components of a Multigraph

Satoshi TAOKA, Toshimasa WATANABE, Kenji ONAGA

Full Text Views

0

Cite this

Summary :

The subject of the paper is to propose a simple O(|V|+|E|) algorithm for finding all 3-edge-components of a given undirected multigraph G=(V, E). An 3-edge-connected component of G is defined as a maximal set of vertices such that G has at least three edge-disjoint paths between every pair of vertices in the set. The algorithm is based on the depth-first search (DFS) technique. For any fixed DFS-tree T of G, cutpairs of G are partitioned into two types: a type 1 pair consists of an edge of T and a back edge; a type 2 pair consists of two edges of T. All type 1 pairs can easily be determined in O(|V|+|E|) time. The point is that an edge set KE(T) in which any type 2 pair is included can be found in O(|V|+|E|) time. All 3-edge-components of G appear as connected components if we delete from G all edges contained in type 1 pairs or in the edge set KE(T).

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.3 pp.410-424

Publication Date: 1992/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on the 4th Karuizawa Workshop on Circuits and Systems)

Category

Cite this

Copy

Satoshi TAOKA, Toshimasa WATANABE, Kenji ONAGA, "A Linear-Time Algorithm for Computing All 3-Edge-Connected Components of a Multigraph" in IEICE TRANSACTIONS on Fundamentals, vol. E75-A, no. 3, pp. 410-424, March 1992, doi: .
Abstract: The subject of the paper is to propose a simple O(|V|+|E|) algorithm for finding all 3-edge-components of a given undirected multigraph G=(V, E). An 3-edge-connected component of G is defined as a maximal set of vertices such that G has at least three edge-disjoint paths between every pair of vertices in the set. The algorithm is based on the depth-first search (DFS) technique. For any fixed DFS-tree T of G, cutpairs of G are partitioned into two types: a type 1 pair consists of an edge of T and a back edge; a type 2 pair consists of two edges of T. All type 1 pairs can easily be determined in O(|V|+|E|) time. The point is that an edge set KE(T) in which any type 2 pair is included can be found in O(|V|+|E|) time. All 3-edge-components of G appear as connected components if we delete from G all edges contained in type 1 pairs or in the edge set KE(T).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_3_410/_p

Copy

@ARTICLE{e75-a_3_410,
author={Satoshi TAOKA, Toshimasa WATANABE, Kenji ONAGA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Linear-Time Algorithm for Computing All 3-Edge-Connected Components of a Multigraph},
year={1992},
volume={E75-A},
number={3},
pages={410-424},
abstract={The subject of the paper is to propose a simple O(|V|+|E|) algorithm for finding all 3-edge-components of a given undirected multigraph G=(V, E). An 3-edge-connected component of G is defined as a maximal set of vertices such that G has at least three edge-disjoint paths between every pair of vertices in the set. The algorithm is based on the depth-first search (DFS) technique. For any fixed DFS-tree T of G, cutpairs of G are partitioned into two types: a type 1 pair consists of an edge of T and a back edge; a type 2 pair consists of two edges of T. All type 1 pairs can easily be determined in O(|V|+|E|) time. The point is that an edge set KE(T) in which any type 2 pair is included can be found in O(|V|+|E|) time. All 3-edge-components of G appear as connected components if we delete from G all edges contained in type 1 pairs or in the edge set KE(T).},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - A Linear-Time Algorithm for Computing All 3-Edge-Connected Components of a Multigraph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 410
EP - 424
AU - Satoshi TAOKA
AU - Toshimasa WATANABE
AU - Kenji ONAGA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1992
AB - The subject of the paper is to propose a simple O(|V|+|E|) algorithm for finding all 3-edge-components of a given undirected multigraph G=(V, E). An 3-edge-connected component of G is defined as a maximal set of vertices such that G has at least three edge-disjoint paths between every pair of vertices in the set. The algorithm is based on the depth-first search (DFS) technique. For any fixed DFS-tree T of G, cutpairs of G are partitioned into two types: a type 1 pair consists of an edge of T and a back edge; a type 2 pair consists of two edges of T. All type 1 pairs can easily be determined in O(|V|+|E|) time. The point is that an edge set KE(T) in which any type 2 pair is included can be found in O(|V|+|E|) time. All 3-edge-components of G appear as connected components if we delete from G all edges contained in type 1 pairs or in the edge set KE(T).
ER -