Report Number: CS-TR-94-1523
Institution: Stanford University, Department of Computer Science
Title: On Implementing Push-Relabel Method for the Maximum Flow
Author: Cherkassky, Boris V.
Author: Goldberg, Andrew V.
Date: September 1994
Abstract: We study efficient implementations of the push-relabel method
for the maximum flow problem. The resulting codes are faster
than the previous codes, and much faster on some problem
families. The speedup is due to the combination of heuristics
used in our implementation. We also exhibit a family of
problems for which all known methods seem to have almost
quadratic time growth rate.