Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428503 | Information Processing Letters | 2015 | 6 Pages |
•We study the problem of computing K-terminal reliability for two subclasses of chordal graphs.•We show that computing the K-terminal reliability of a directed path graph is #P-complete.•We propose an O(n2)O(n2)-time algorithm for computing the K-terminal reliability of a rooted directed path graph.
Let G denote a graph, and K⊆V(G)K⊆V(G) represent a set of target vertices. Assume that the non-target vertices of G fail independently with given probabilities. The K-terminal reliability of G is defined as the probability that all target vertices in K are connected. Computing K-terminal reliability is #P-complete for chordal graphs, yet solvable in polynomial time for its subclass of interval graphs. While improving both of these results, this work demonstrates that although the problem remains #P-complete when restricted to directed path graphs, a further restriction to rooted directed path graphs yields a polynomial time solution.