Computing 2-terminal reliability of probe interval graphs
Chao-Chun Ting, Min-Sheng Lin · Applied Mathematical Sciences · 2015
Copyright © 2014 Chao-Chun Ting and Min-Sheng Lin. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Consider a probabilistic graph G in which the edges are perfectly reliable, but vertices may fail with some known probabilities. The 2-terminal reliability of G is defined as the probability that one operational path exists between a given source and destination pair vertices of G. This 2-terminal reliability problem is known to be #P-complete for general graphs but solvable in polynomial time for interval graphs. This work presents a polynomial-time algorithm for computing the 2-terminal reliability of probe interval graphs, which is a superclass of interval graphs.