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

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,k2}n2d)-time algorithm for computing the K-terminal residual reliability of a d-trapezoid graph G, where n=|V(G)| and k=|K|.