@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",

}