The SKT reliability is the probability that a source can send communication to a specified set of terminals K in V in a probabilistic digraph D = (V, E). ''The most vital edge'' is the edge whose delet...
详细信息
The SKT reliability is the probability that a source can send communication to a specified set of terminals K in V in a probabilistic digraph D = (V, E). ''The most vital edge'' is the edge whose deletion yields the largest decrease in the SKT reliability. A digraph is a basically-series-parallel(BSP) directed graph if its underlying undirected graph is series-parallel. In this paper, we propose a tree-like structure and present an optimal algorithm with linear time complexity for finding the most vital edge with respect to SKT reliability in BSP digraphs.
暂无评论