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 K-Terminal Reliability of Circular-Arc Graphs
Chien-Min CHEN Min-Sheng LIN
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/12/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
algorithm, reliability, circular-arc graphs, interval graphs,
Full Text: PDF>>
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.