
For FullText 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 MultiTolerance Graphs
ChienMin CHEN MinSheng LIN
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E99D
No.7
pp.17331741 Publication Date: 2016/07/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2015EDP7418
Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: algorithm, reliability, multitolerance graph, trapezoid graph,
Full Text: PDF>>
Summary:
Let G be a probabilistic graph, in which the vertices fail independently with known probabilities. Let K represent a specified subset of vertices. The Kterminal reliability of G is defined as the probability that all vertices in K are connected. When K=2, the Kterminal reliability is called the 2terminal reliability, which is the probability that the source vertex is connected to the destination vertex. The problems of computing Kterminal reliability and 2terminal reliability have been proven to be #Pcomplete in general. This work demonstrates that on multitolerance graphs, the 2terminal reliability problem can be solved in polynomialtime and the results can be extended to the Kterminal reliability problem on bounded multitolerance graphs.

