Reducing edge connectivity to vertex connectivity
- 1 March 1991
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 22 (1) , 57-61
- https://doi.org/10.1145/122413.122416
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 9 references indexed in Scilit:
- A matroid approach to finding edge connectivity and packing arborescencesPublished by Association for Computing Machinery (ACM) ,1991
- Finding the edge connectivity of directed graphsJournal of Algorithms, 1989
- Improved algorithms for graph four-connectivityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,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 THEORYPublished by Defense Technical Information Center (DTIC) ,1969