A Method for Obtaining the Maximum δ-Reliable Flow in a Network

Wataru KISHIMOTO  Masashi TAKEUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.5   pp.776-783
Publication Date: 1998/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
network,  δ-reliable flow,  δ-reliable capacity of a cut,  Max-flow min-cut theorem,  

Full Text: PDF(615.6KB)>>
Buy this Article




Summary: 
In communication networks there is a growing need for ensuring that networks maintain service despite failures. To meet the need, the concept of δ-reliable channel is introduced; it is a set of communication channels along a set of paths. The δ-reliable channel meets the requirement that if a link or node fails, failure is limited to a maximum of δ f (f total capacity of the channels, and 0<δ 1). The max-flow min-cut theorem of δ-reliable flow has been proved for the single-commodity case. In this paper we give a method for evaluating the maximum δ-reliable flow between a specified pair of vertices for single commodity case. The method consists of a maximum of 1/δ iterations of calculations of the maximum flow value.