CODEWITHSUNDEEP
graphgraph-theoryminimum-cut
David Norman
David Norman

Reputation: 19889

Algorithm for splitting a connected graph into two components

Suppose I am given a weighted, connected graph. I'd like to find a list of edges that can be removed from the graph leaving it split into two components and so that the sum of the weights of the removed edges is small. Ideally I'd like to have the minimal sum, but I'd settle for a reasonable approximation.

This seems like a hard problem. Are there any good algorithms for doing this?

If it helps, in my case the number of nodes is about 50 and the graph may be dense, so that most pairs of nodes will have an edge between them.

Upvotes: 3

Views: 7655

Answers (3)

Goktug
Goktug

Reputation: 923

I may be wrong with my idea, but Ford Fulkersonalgorithm does not find a solution for this problem, since Ford Fulkerson assumes that there are source and destination nodes, and there is an attempt to transfer a material from source to destination. Hence, the algorithm cannot calculate all possible min-cuts.

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363777

I believe what you're looking for is an algorithm for computing the minimum cut. The Edmonds-Karp algorithm does this for flow networks (with source and sink vertices). Hao and Orlin (1994) generalize this to directed, weighted graphs. Their algorithm runs in O(nm lg(n^2/m)) for n vertices and m edges. Chekuri et al. (1997) compare several algorithms empirically, some of which have better big O's than Hao and Orlin.

Upvotes: 3

Steve Tjoa
Steve Tjoa

Reputation: 61094

I think you are looking for a minimum cut algorithm. Wikipedia

Before the Edmunds-Karp algorithm came the Ford-Fulkerson algorithm. For what it's worth, the Algorithms book [Cormen, Rivest] cites these two algorithms in the chapter on graph theory.

Upvotes: 3

Related Questions