Simple generalized maximum flow algorithms

Éva Tardos, Kevin D. Wayne

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

30 Scopus citations

Abstract

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
Pages310-324
Number of pages15
ISBN (Print)354064590X, 9783540645900
DOIs
StatePublished - Jan 1 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)
Volume1412
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998
CountryUnited States
CityHouston
Period6/22/986/24/98

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Tardos, É., & Wayne, K. D. (1998). Simple generalized maximum flow algorithms. In E. Andrew Boyd, R. E. Bixby, & R. Z. Rios-Mercado (Eds.), Integer Programming and Combinatorial Optimization - 6th International IPCO Conference, 1998, Proceedings (pp. 310-324). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1412). Springer Verlag. https://doi.org/10.1007/3-540-69346-7_24