Improving time bounds on maximum generalised flow computations by contracting the network
✍ Scribed by Tomasz Radzik
- Publisher
- Elsevier Science
- Year
- 2004
- Tongue
- English
- Weight
- 451 KB
- Volume
- 312
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
We consider the maximum generalised network ow problem and a supply-scaling algorithmic framework for this problem. We present three network-modiÿcation operations, which may signiÿcantly decrease the size of the network when the remaining node supplies become small. We use these three operations in Goldfarb et al.'s supply-scaling algorithm and prove an Õ(m 2 n log B) bound on the running time of the resulting algorithm. The previous best time bounds on computing maximum generalised ows are the O(m 1:5 n 2 log B) bound of Kapoor and Vaidya's algorithm based on the interior-point method, and the Õ(m 3 log B) bound of Goldfarb et al.'s algorithm.