@inproceedings{567ad4c1833a497e91f9f5dfc7bdb743,

title = "Balancing applied to maximum network flow problems (extended abstract)",

abstract = "We explore balancing as a definitional and algorithmic tool for finding minimum cuts and maximum flows in ordinary and parametric networks. We show that a standard monotonic parametric maximum flow problem can be formulated as a problem of computing a particular maximum flow that is balanced in an appropriate sense. We present a divide-and-conquer algorithm to compute such a balanced flow in a logarithmic number of ordinary maximum-flow computations. For the special case of a bipartite network, we present two simple, local algorithms for computing a balanced flow. The local balancing idea becomes even simpler when applied to the ordinary maximum flow problem. For this problem, we present a round-robin arc-balancing algorithm that computes a maximum flow on an n-vertex, m-arc network with integer arc capacities of at most U in O(n 2m log(nU)) time. Although this algorithm is slower by at least a factor of n than other known algorithms, it is extremely simple and well-suited to parallel and distributed implementation.",

author = "Robert Tarjan and Julie Ward and Bin Zhang and Yunhong Zhou and Jia Mao",

year = "2006",

month = jan,

day = "1",

doi = "10.1007/11841036_55",

language = "English (US)",

isbn = "3540388753",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "612--623",

booktitle = "Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings",

address = "Germany",

note = "14th Annual European Symposium on Algorithms, ESA 2006 ; Conference date: 11-09-2006 Through 13-09-2006",

}