ON IMPLEMENTING THE PUSH-RELABEL METHOD FOR THE MAXIMUM FLOW PROBLEM

Authors
CHERKASSKY BV GOLDBERG AV
Citation
Bv. Cherkassky et Av. Goldberg, ON IMPLEMENTING THE PUSH-RELABEL METHOD FOR THE MAXIMUM FLOW PROBLEM, Algorithmica, 19(4), 1997, pp. 390-410
Citations number
24
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
19
Issue
4
Year of publication
1997
Pages
390 - 410
Database
ISI
SICI code
0178-4617(1997)19:4<390:OITPMF>2.0.ZU;2-K
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 t o the combination of heuristics used in our implementations: we show t hat the highest-level selection strategy gives better results when com bined with both global and gap relabeling heuristics. We also exhibit a family of problems for which the running time of all implementations we consider is quadratic.