Minimum cut

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
New poster
Posts: 9
Joined: Sat Apr 15, 2006 6:07 pm

Minimum cut

Post by blowguy »

I know some algorithms how to find minimum cut in a graph, but is there an algorithm that gives the set of edges that form the min cut?

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »


This question has been asked before here. Check this out:

In short, by the famous Maxflow-mincut theorem, you can get a mincut (a partition of the original graph) from a maxflow. Please go through the proof of the theorem again.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)

Post Reply

Return to “Algorithms”