@inproceedings{4ac8627e274041a88e6359e1e3c62225,
title = "Simple generalized maximum flow algorithms",
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.",
author = "{\'E}va Tardos and Wayne, {Kevin D.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1998.; 6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998 ; Conference date: 22-06-1998 Through 24-06-1998",
year = "1998",
doi = "10.1007/3-540-69346-7_24",
language = "English (US)",
isbn = "354064590X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "310--324",
editor = "{Andrew Boyd}, E. and Bixby, {Robert E.} and Rios-Mercado, {Roger Z.}",
booktitle = "Integer Programming and Combinatorial Optimization - 6th International IPCO Conference, 1998, Proceedings",
address = "Germany",
}