Goldberg's Network Optimization Codes
The highest performance codes available for such network optimization
problems as matching, shortest paths, and network flow have been developed
by Andrew Goldberg and his collaborators.
All are written in C.
Their codes are available by ftp for non-commercial use,
although a license is required for commercial use.
For information on obtaining the codes,
check out Andrew Goldberg's WWW page,
http://www.avglab.com/andrew/soft.htmlTheir implementations of both Dijkstra and Bellman-Ford's algorithms
for finding
shortest paths in graphs is SPLIB,
developed by Cherkassky, Goldberg, and Radzik.
They report solving instances with over one million vertices
in under two minutes on a Sun Sparc-10 workstation.
Their code
for finding a maximum cardinality bipartite matching of
maximum weight shortest paths in graphs is CSA,
developed by Goldberg and Kennedy.
This code is based on a cost-scaling network flow algorithms.
Their running times depend upon the density of the networks and weight
distributions, but they report solving instances with over 30,000 vertices
in a few minutes on a Sun Sparc-2 workstation.
Their code for
solving maximum-flow in graphs is PRF,
developed by Cherkassky and Goldberg.
They report solving instances with over 250,000 vertices
in under two minutes on a Sun Sparc-10 workstation.
For minimum-cost max-flow, the higher performance code available is
CS, capable of solving instances of over 30,000 vertices
in a few minutes on Sun Sparc-2 workstations.
Download Files (local site)Andrew V. Goldberg's HomepageAndrew Goldberg's Network Optimization Library page
Problem Links
This page last modified on 2008-07-10
.
www.algorist.com
