Reducing edge connectivity to vertex connectivity
Authors:
Open Access
- 1 March 1991
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 22 (1) , 57-61
Abstract
We show how to reduce edge connectivity to vertex connectivity. Using this reduction, we obtain a linear-time algorithm for deciding whether an undirected graph is 3-edge-connected, and for computing the 3-edge-connected components of an undirected graph.Keywords
This publication has 10 references indexed in Scilit:
- A matroid approach to finding edge connectivity and packing arborescences1991
- Finding the edge connectivity of directed graphsJournal of Algorithms, 1989
- Improved algorithms for graph four-connectivity1987
- Determining edge connectivity in 0(nm)1987
- Finding the Vertex Connectivity of GraphsSIAM Journal on Computing, 1980
- Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, 1975
- An Algorithm for Determining Whether the Connectivity of a Graph is at LeastkSIAM Journal on Computing, 1975
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- GRAPH THEORY1969