Implementing Push-Relabel Method for the Maximum Flow Problem

摘要

The authors study efficient implementations of the push-relabel method for themaximum 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 the authors implementation. They also exhibit a family of problems for which all known methods seem to have almost quadratic time growth rate.