### 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 ^{2}m 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 language | English (US) |
---|---|

Title of host publication | Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 612-623 |

Number of pages | 12 |

ISBN (Print) | 3540388753, 9783540388753 |

DOIs | |

State | Published - Jan 1 2006 |

Event | 14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland Duration: Sep 11 2006 → Sep 13 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4168 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 14th Annual European Symposium on Algorithms, ESA 2006 |
---|---|

Country | Switzerland |

City | Zurich |

Period | 9/11/06 → 9/13/06 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

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

## Cite this

*Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings*(pp. 612-623). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4168 LNCS). Springer Verlag. https://doi.org/10.1007/11841036_55