The Algorithms
and Data Structures Group of the University of Trier in Germany
has made some tests in order to compare different available maxflow
implementations.
 The
Competitors
Boost
BGL
A graph library available at http://www.boost.org/libs/graph/doc/table_of_contents.html
Hi_Pr
3.5
This is a highly optimized C-implementation of
the push-relabel method, following Goldberg and Tarjan, "A
New Approach to the Maximum Flow Problem," J. ACM Vol. 35,
921--940, 1988
and
Cherkassky and Goldberg, "On Implementing Push-Relabel Method for the
Maximum Flow Problem," Proc. IPCO-4, 157--171, 1995.
LEDA
5.0
A commercial graph library available at http://www.algorithmic-solutions.com
The
Test Platform
2 x Ultra Sparc III (1.2GHz), 2048 MB RAM; Compiler:
GCC-3.4.2 -O2
Problem
Instances and Results
Three different types of networks have been tested.
See the results for:
|
