Improved algorithms for graph four-connectivity
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 252-259
- https://doi.org/10.1109/sfcs.1987.33
Abstract
We present a new algorithm based on ear decomposition for testing vertex four-connectivity and for finding all separating triplets in a triconnected graph. The sequential implementation of our algorithm runs in O(n2) time and the parallel implementation runs in O(logn) time using O(n2) processors on a CRCW PRAM, where n is the number of vertices in the graph. This improves previous bounds for the problem for both the sequential and parallel cases. The sequential algorithm is optimal if the input is specified in adjacency matrix form, or if the input graph is dense.Keywords
This publication has 12 references indexed in Scilit:
- A new graph triconnectivity algorithm and its parallelizationCombinatorica, 1992
- A physical interpretation of graph connectivity, and its algorithmic applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Parallel ear decomposition search (EDS) and st-numbering in graphsPublished by Springer Nature ,1986
- An Efficient Parallel Biconnectivity AlgorithmSIAM Journal on Computing, 1985
- Computing ears and branchings in parallelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- 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
- Non-separable and planar graphsTransactions of the American Mathematical Society, 1932