Article ID Journal Published Year Pages File Type
10331920 Information Processing Letters 2015 6 Pages PDF
Abstract
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|.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs
Authors
, ,