Simple generalized maximum flow algorithms

Éva Tardos, Kevin D. Wayne

Research output: Chapter in Book/Report/Conference proceedingConference contribution

35 Scopus citations


We introduce a gain-scaling technique for the generalized maximum flow problem. Using this technique, we present three simple and intuitive polynomial-time combinatorial algorithms for the problem. Truemper's augmenting path algorithm is one of the simplest combinatorial algorithms for the problem, but runs in exponential-time. Our first algorithm is a polynomial-time variant of Truemper's algorithm. Our second algorithm is an adaption of Goldberg and Tarjan's preflowpush algorithm. It is the first polynomial-time preflow-push algorithm in generalized networks. Our third algorithm is a variant of the Fat-Path capacity-scaling algorithm. It is much simpler than Radzik's variant and matches the best known complexity for the problem.We discuss practical improvements in implementation.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 6th International IPCO Conference, 1998, Proceedings
EditorsE. Andrew Boyd, Robert E. Bixby, Roger Z. Rios-Mercado
PublisherSpringer Verlag
Number of pages15
ISBN (Print)354064590X, 9783540645900
StatePublished - 1998
Externally publishedYes
Event6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998 - Houston, United States
Duration: Jun 22 1998Jun 24 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Simple generalized maximum flow algorithms'. Together they form a unique fingerprint.

Cite this