Re: [boost] [SoC][BGL] new mincut/maxflow algorithm

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:
> http://mp-vipa5.informatik.uni-mannheim.de/~diederich/data/soc/doc/kolmogorov_max_flow.html
>
> The goal of the project was to have an algorithm with a runtime which is
> comparable to other standard maxflow/mincut implementations.
> Performance measurements
> (http://stephan.diederich.googlepages.com/soc2006222) 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).

Stephan,

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!

Aaron