Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer SciencesVol.E81-ANo.5pp.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)>>
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.