page 1  (23 pages)
2to next section

ON IMPLEMENTING PUSH-RELABEL METHOD
FOR THE MAXIMUM FLOW PROBLEM

BORIS V. CHERKASSKY

CENTRAL INSTITUTE FOR ECONOMICS AND MATHEMATICS
KRASIKOVA ST. 32, 117418, MOSCOW, RUSSIA
CHER@CEMI.MSK.SU

ANDREW V. GOLDBERG

COMPUTER SCIENCE DEPARTMENT, STANFORD UNIVERSITY
STANFORD, CA 94305, USA
GOLDBERG@CS.STANFORD.EDU

October 1994; revised April 1995

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 implementations: we show that the highest-level selection strategy gives better results when combined 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.

Keywords: algorithms, network optimization, maximum flows, experimental evaluation.

Andrew V. Goldberg was supported in part by NSF Grant CCR-9307045 and a grant from Powell Foundation. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the above-mentioned NSF and Powell Foundation grants.