On computing the connectivities of graphs and digraphs
- 1 June 1984
- Vol. 14 (2) , 355-366
- https://doi.org/10.1002/net.3230140211
Abstract
In this paper methods are described that will compute the edge‐connectivity of a graph or a digraph at least twice as fast as the known methods. A study of the computation of the vertex‐connectivity is presented which leads to new algorithms for this purpose or for the purpose of determining if the vertex‐connectivity is at least k. These algorithms compare favorably with Kleitman's, Even's, Even and Tarjan's, and Galil's algorithms.Keywords
This publication has 5 references indexed in Scilit:
- Finding the Vertex Connectivity of GraphsSIAM Journal on Computing, 1980
- Bottlenecks and Edge Connectivity in Unsymmetrical NetworksSIAM Journal on Computing, 1979
- 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
- Methods for Investigating Connectivity of Large GraphsIEEE Transactions on Circuit Theory, 1969