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:

LEDA large

is LEDA's standard (general purpose) graph type that needs 16n + 12m words of memory.

LEDA small

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:

• UltraSPARC IIi 440 Mhz

• Athlon 700 Mhz

• Pentium II 450 Mhz

• AMD K6 II 400 Mhz