On Multiroute Maximum Flows in Networks

Abstract

Let G = (N, A) be a network with a designated source node s, a designated sink node t, and a finite integral capacity uij on each arc (i, j) ∈ A. An elementary K-flow is a flow of K units from s to t such that the flow on each arc is 0 or 1. A K-route flow is a flow from s to t that may be expressed as a nonnegative linear sum of elementary K-flows. In this paper, we show how to determine a maximum K-route flow as a sequence of O(min {log (nU), K}) maximum-flow problems. This improves upon the algorithm by Kishimoto, which solves this problem as a sequence of K maximum-flow problems. In addition, we have simplified and extended some of the basic theory. We also discuss the application of our technique to Birkhoff's theorem and a scheduling problem. © 2001 John Wiley & Sons, Inc.