Re: [boost] [BGL] Stoer–Wagner min-cut algorithm

Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
From: Dan Jiang (danjiang_at_[hidden])
Date: 2010-07-05 11:24:02

> Date: Mon, 5 Jul 2010 08:10:10 -0400
> From: dtrebbien_at_[hidden]
> To: boost_at_[hidden]
> Subject: Re: [boost]	[BGL] Stoer–Wagner min-cut algorithm
> 
> > [snip]
> > Are you sure that you don't want me to add "min-cut" to the maximum flow
> > section title and then put your code in there?  How related is your code
> > to standard max-flow algorithms?
> 
> I don't think that a section on min-cuts should go *in* the section on
> maximum flow algorithms because although the two are related, a
> min-cut algorithm does not need to exploit the duality of maximum
> flow/weight of minimum cut. In fact, the Stoer–Wagner algorithm does
> not, and a number of recent algorithms do not.
> 
Hi Daniel,
I wonder if your min-cut algorithm can be used to find max flow, since min-cut and max-flow are dual? I am currently using two max-flow implementations in BOOST (i.e, Goldberg and Kolmogorov). What is the complexity compared to the two max-flow implementations in BOOST. I am looking for fastest max flow implementation available. 
Another related question: does BOOST offer parallel implementation of any max-flow algorithm?
Thanks
Dan 		 	   		  
_________________________________________________________________
Look 'em in the eye: FREE Messenger video chat
http://go.microsoft.com/?linkid=9734386