Subject: Re: [boost] [BGL] StoerWagner 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] StoerWagner 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 StoerWagner algorithm does
> not, and a number of recent algorithms do not.
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?
Look 'em in the eye: FREE Messenger video chat
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk