Browsing by Author "LEU, SC"

Now showing 1 - 1 of 1

AN OPTIMAL ALGORITHM FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO SKT RELIABILITY IN BSP DIGRAPHS
(1995-07-01)
WANG, PF
;
LEU, SC
;
HSU, LH
;
資訊工程學系
;
Department of Computer Science
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.