| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427163 | Information Processing Letters | 2013 | 5 Pages |
•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.
