CODEWITHSUNDEEP
javaalgorithmgraphgraph-theory
PrakashSharma
PrakashSharma

Reputation: 386

How to find edge connectivity between 2 given vertex

Edge connectivity is minimum number of edge to be removed to divide graph in 2 or more components. As of now I have found an algorithm for edge connectivity irrespective of vertex: http://www.sanfoundry.com/java-program-find-edge-connectivity-graph/

What is the best method I can use to proceed with, to find the edge connectivity between 2 vertices?

Edge Connectivity between 2 vertex(v1, v2) - Means

If cutting any edge/edges in Graph G, generates two components G1 & G2.

Here ( v1 ∈ G1 and v2 ∈ G2 ) OR ( v2 ∈ G1 and v1 ∈ G2 )

Upvotes: 1

Views: 1271

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58389

You're describing the minimum cut problem. It's equivalent to finding the maximum flow, and the Ford Fulkerson algorithm can find it.

Upvotes: 2

Related Questions