On 8/28/06, Stephan Diederich <S.Diederich@gmx.de> 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/kolmogoro...
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