Minimum cut

Let's talk about algorithms!

Moderator: Board moderators

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

Minimum cut

Post by blowguy » Sat Jun 09, 2007 9:11 pm

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?

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

Post by Observer » Mon Jun 11, 2007 12:26 pm

Hi,

This question has been asked before here. Check this out:
http://online-judge.uva.es/board/viewtopic.php?t=2537

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)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Algorithms”