Date: Mon, 5 Jul 2010 08:10:10 -0400 From: dtrebbien@gmail.com To: boost@lists.boost.org 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