Computing K-Terminal Reliability of Circular-Arc Graphs

Chien-Min CHEN  Min-Sheng LIN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.12   pp.3047-3052
Publication Date: 2016/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016EDP7221
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
algorithm,  reliability,  circular-arc graphs,  interval graphs,  

Full Text: PDF>>
Buy this Article




Summary: 
Let G be a graph and K be a set of target vertices of G. Assume that all vertices of G, except the vertices in K, may fail with given probabilities. The K-terminal reliability of G is the probability that all vertices in K are mutually connected. This reliability problem is known to be #P-complete for general graphs. This work develops the first polynomial-time algorithm for computing the K-terminal reliability of circular-arc graphs.