Skip to main content
SpringerLink
Log in

On Implementing the Push—Relabel Method for the Maximum Flow Problem

  • Published:
Algorithmica Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

  1. Central Institute for Economics and Mathematics, Krasikova St. 32, 117418 Moscow, Russia. cher@cemi.msk.su., , , , , , RU

    B. V. Cherkassky

  2. Computer Science Department, Stanford University, Stanford, CA 94305, USA. goldberg@cs.stanford.edu. Current address: NEC Research Institute Inc., 4 Independence Way, Princeton, NJ 08540, USA. avg@research.nj.nec.com., , , , , , US

    A. V. Goldberg

Authors
  1. B. V. Cherkassky
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. V. Goldberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Received October 24, 1994; revised April 25, 1995.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cherkassky, B., Goldberg, A. On Implementing the Push—Relabel Method for the Maximum Flow Problem . Algorithmica 19, 390–410 (1997). https://doi.org/10.1007/PL00009180

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/PL00009180

Search

Navigation