Boost logo

Boost :

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2006-08-30 06:57:48

On 8/28/06, Stephan Diederich <S.Diederich_at_[hidden]> wrote:
> Hello,
> with this mail I want to point to my work done during this year's SoC:
> "Implementing a state of the art mincut/maxflow algorithm".
> Mentored by Douglas Gregor I implemented a maxflow/mincut algorithm
> for BGL which was originally presented by Vladimir Kolmogorov[1].
> The documentation and description of the implementation can be found at:
> The goal of the project was to have an algorithm with a runtime which is
> comparable to other standard maxflow/mincut implementations.
> Performance measurements
> ( show that this
> goal was reached.
> What can be read from those charts is, that the runtime of the
> algorithms clearly depends on the underlying problem type. For graphs
> found in image segmentation problems and random graphs, the newly
> developed algorithm outperforms the existing alternative(s).


Thanks! Looks like a very good implementation. Can you elaborate a little
on your experimentation? What are ac-graphs and ak(i)-graphs, and what
parameters did you use to generate the random graphs?

I skimmed Komolgorov's thesis, and based on his experiments, it seems
that this is a very efficient algorithm for 2-D and 3-D grid graphs arising in
image processing applications - did you get a sense for what other types
of graphs this algorithm might be competitive on? Maybe graphs with low
degree in general?

Thanks again for your contribution!


Boost list run by bdawes at, gregod at, cpdaniel at, john at