Computing K-terminal reliability of d-trapezoid graphs

• We study the problem of computing K-terminal reliability for some restricted graphs.
• We propose an O(n2d+1)O(n2d+1)-time algorithm for d-trapezoid graphs.
• We propose an O(n2)O(n2)-time algorithm for interval graphs.

Consider a probabilistic graph in which the edges are perfectly reliable, but vertices may fail with some known probabilities. The K-terminal reliability of this graph is the probability that a given set of vertices K   are connected to each other. This reliability problem is known to be #P-complete for general graphs, and it remains #P-complete for chordal graphs and comparability graphs. This work proposes an O(n2d+1)O(n2d+1)-time algorithm for computing the K-terminal reliability of d  -trapezoid graphs. With some modifications, the algorithm is executed in O(n2)O(n2) time for interval graphs.