On a realization problem from non-terminal capacity matrices on undirected flow networks
✍ Scribed by Hiroshi Tamura; Masakazu Sengoku; Shoji Shinoda; Takeo Abe
- Publisher
- John Wiley and Sons
- Year
- 2001
- Tongue
- English
- Weight
- 309 KB
- Volume
- 84
- Category
- Article
- ISSN
- 1042-0967
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
The problem of realizing a given matrix on an undirected flow network has been studied and various results have been obtained. Most of these results consist of necessary and sufficient conditions for methods of realization in which the maximum good flow between the two points and the matrix components coincide. However, there are cases in which coincidence is not required as long as they are close to each other. In this paper, we consider the realization under certain conditions when values not necessarily realizable as maximum good flows of the flow network are given between two points. First, the upper and lower bounds of the maximum good flow are given. The problem of realization between these two extremes is studied and the necessary and sufficient condition is given. Next, by means of this result, we consider the problem of minimizing the difference between the given value and the maximum good flow in the undirected flow network. A realization method is studied. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(12): 28–39, 2001