Computing K-terminal reliability of d-trapezoid graphs

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

来源：Information Processing Letters, 2013, 113(19-21): 734-738.

DOI：10.1016/j.ipl.2013.07.006

• Algorithms
• Reliability
• d-trapezoid graph
• Interval graph

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(n(2d+1))-time algorithm for computing the K-terminal reliability of d-trapezoid graphs. With some modifications, the algorithm is executed in O(n(2)) time for interval graphs.

• 出版日期2013-10