ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryTopologyConnectivity AnalysisGraph AlgorithmsGraph AnalyticsGraph TheoryComputational Complexity Of Graph AlgorithmsConnectivity AlgorithmsGraph ConnectivityGraph Connectivity AnalysisVertex Connectivity
We describe an algorithm that determines the edge connectivity of an n-vertex m-edge graph G in O(nm) time. A refinement shows that the question as to whether a graph is k-edge connected can be determined in O(kn2). For dense graphs characterized by m = Ω(n2), the latter result implies that determination of whether a graph is k-edge connected for any fixed k can be accomplished in time linear in input size.
7
Network Flow and Testing Graph Connectivity
Shimon Even, Robert E. Tarjan · SIAM Journal on Computing · 1975 · 558 citations
Finding the Vertex Connectivity of Graphs
Zvi Galil · SIAM Journal on Computing · 1980 · 90 citations
On computing the connectivities of graphs and digraphs
Abdol H. Esfahanian, S. L. Hakimi · Networks · 1984 · 48 citations