Dividing a Graph into Triconnected Components
Authors:
- J. E. HopcroftJHJ. E. Hopcroft
- R. E. TarjanRTR. E. Tarjan
- 1 September 1973
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 2 (3) , 135-158
Abstract
An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires $O(V + E)$ time and space to analyze a graph with V vertices and E edges. The algorithm is both theoretically optimal to within a constant factor and efficient in practice.
Keywords
This publication has 7 references indexed in Scilit:
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- Decomposition of a graph into compactly connected two-terminal subgraphsIEEE Transactions on Circuit Theory, 1971
- A new planarity test based on 3-connectivityIEEE Transactions on Circuit Theory, 1970
- GRAPH THEORY1969
- Methods for Investigating Connectivity of Large GraphsIEEE Transactions on Circuit Theory, 1969
- Connectivity in Graphs1966
- A structural characterization of planar combinatorial graphsDuke Mathematical Journal, 1937