岸本 渡

In communication networks there is a growing need for ensuring that networks maintain service despite failures. To meet this need, the concept of delta-reliable channel is introduced; it is a set of communication channels along a set of paths. The delta-reliable channel meets the requirement that if a link or node fails, failure is limited to a maximum of delta . c (c = total capacity of the channels, and 0 < delta less than or equal to 1). A delta-reliable flow is such that the maximum number of flow failures is delta . f (f = value of the flow) of an edge or vertex of a network fails. The max-flow min-cut theorem of delta-reliable flow is demonstrated for the single-commodity case.

In a communication network, a multiroute channel is more reliable than is an ordinary channel against link or terminal failures. An m-route Row corresponds to a set of m-route channels, where m is the number of disjoint paths the m-route channel passes through. The max-flow min-cut theorem of the m-route flow has been proved by Kishimoto and Takeuchi. We show how to obtain the maximum m-route flow between two vertices. First, we evaluate the maximum value of m-route Rows between two vertices by at most m times calculations of the maximum value of ordinary flows. Then, we construct the m-route flow with the maximum value. The correctness of this method gives another proof of Kishimoto and Takeuchi's max-flow min-cut theorem. The maximum value of m-route Rows corresponds to the maximum capacity by m-route channels between two terminals. (C) 1996 John Wiley & Sons, Inc.