Computing Terminal Reliability of Multi-Tolerance Graphs

Chien-Min CHEN  Min-Sheng LIN  

IEICE TRANSACTIONS on Information and Systems   Vol.E99-D    No.7    pp.1733-1741
Publication Date: 2016/07/01
Publicized: 2016/04/13
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015EDP7418
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
algorithm,  reliability,  multi-tolerance graph,  trapezoid graph,  

Full Text: PDF>>
Buy this Article

Let G be a probabilistic graph, in which the vertices fail independently with known probabilities. Let K represent a specified subset of vertices. The K-terminal reliability of G is defined as the probability that all vertices in K are connected. When |K|=2, the K-terminal reliability is called the 2-terminal reliability, which is the probability that the source vertex is connected to the destination vertex. The problems of computing K-terminal reliability and 2-terminal reliability have been proven to be #P-complete in general. This work demonstrates that on multi-tolerance graphs, the 2-terminal reliability problem can be solved in polynomial-time and the results can be extended to the K-terminal reliability problem on bounded multi-tolerance graphs.