کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427163 | 686460 | 2013 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Computing K-terminal reliability of d-trapezoid graphs Computing K-terminal reliability of d-trapezoid graphs](/preview/png/427163.png)
• We study the problem of computing K-terminal reliability for some restricted graphs.
• We propose an O(n2d+1)O(n2d+1)-time algorithm for d-trapezoid graphs.
• We propose an O(n2)O(n2)-time algorithm for interval graphs.
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(n2d+1)O(n2d+1)-time algorithm for computing the K-terminal reliability of d -trapezoid graphs. With some modifications, the algorithm is executed in O(n2)O(n2) time for interval graphs.
Journal: Information Processing Letters - Volume 113, Issues 19–21, September–October 2013, Pages 734–738