A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs

作者：Lin Min Sheng^*; Ting Chao Chun

来源：Information Processing Letters, 2015, 115(2): 371-376.

DOI：10.1016/j.ipl.2014.10.013

• Algorithms
• Combinatorial problems
• K-terminal residual reliability
• d-Trapezoid graphs

Consider a probabilistic graph G in which the edges of E(G) are perfectly reliable, but the vertices of V(G) may fail with some known probabilities. Given a subset K of V (G), the K-terminal residual reliability of G is the probability that all operational vertices in K are connected to each other. This problem can be considered to be a generalization of two well-known reliability problems - the K-terminal reliability problem and the residual connectedness reliability problem.
The K-terminal residual reliability problem is known to be #P-complete for general graphs; it is also #P-complete for chordal graphs, comparability graphs, split graphs and bipartite planar graph. This paper develops an O(max{n, k(2)}n(2d))-time algorithm for computing the K-terminal residual reliability of a d-trapezoid graph G, where n = vertical bar V (G)vertical bar and k = vertical bar K vertical bar.

• 出版日期2015-2