On multiroute maximum flows in networks

✍ Scribed by Charu C. Aggarwal; James B. Orlin

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 172 KB
• Volume: 39
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.10008

✦ Synopsis

Abstract

Let G = (N, A) be a network with a designated source node s, a designated sink node t, and a finite integral capacity u~ij~ 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 arcis 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.