Balancing applied to maximum network flow problems (extended abstract)

Robert Tarjan, Julie Ward, Bin Zhang, Yunhong Zhou, Jia Mao

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

14 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages612-623
Number of pages12
ISBN (Print)3540388753, 9783540388753
DOIs
StatePublished - 2006
Event14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland
Duration: Sep 11 2006Sep 13 2006

Publication series

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

Other

Other14th Annual European Symposium on Algorithms, ESA 2006
Country/TerritorySwitzerland
CityZurich
Period9/11/069/13/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Balancing applied to maximum network flow problems (extended abstract)'. Together they form a unique fingerprint.

Cite this