This page contains the results of a comparison between the preflow-push maxflow code of
Cherkassky/Goldberg (http://www.intertrust.com/star/goldberg/soft.html) and the LEDA
(http://www.mpi-sb.mpg.de/LEDA) implementation as described in chapter 7.10 of the LEDA
book (http://www.mpi-sb.mpg.de/~mehlhorn/LEDAbook.html) on four different hardware
platforms (follow the corresponding links at the end of this page). In this experiment the LEDA
code has been used with two different graph data structures:
is LEDA's standard (general purpose) graph type that needs 16n + 12m words of memory.
is based on a smaller static graph data structure that needs only 8n + 7m words of memory.
Note that both data structures have been used with exactly the same maxflow source code
(LEDAROOT/incl/templates/max_flow.t). We used Goldberg's ak-Generator to create
difficult and large maxflow problems (ak(i) for i=1,000 to 50,000). The experiments show
that the large standard graph type (LEDA large) causes a slow-down by a factor of less than
two compared to the Cherkassky/Goldberg implementation whereas the new static and smaller
graph data structure (LEDA small) achieves about the same running time as CG (on some machines
it is slightly slower, on others slightly faster).
Follow these links to see the results for a particular hardware platform: