For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computing Terminal Reliability of Multi-Tolerance Graphs
Chien-Min CHEN Min-Sheng LIN
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/07/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
algorithm, reliability, multi-tolerance graph, trapezoid graph,
Full Text: PDF(979.1KB)>>
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.