Browsing by Author "WANG, PF"

Now showing 1 - 6 of 6

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.
FINDING THE MOST VITAL EDGE WITH RESPECT TO K-TERMINAL RELIABILITY IN SERIES-PARALLEL NETWORKS
(1993-09-01)
WANG, PF
;
HSU, LH
;
資訊工程學系
;
Department of Computer Science
Let K be contained in the vertex-set of a graph G. ''The most vital edge'' is the edge whose deletion yields the largest decrease in the K-terminal reliability, that is the probability that all vertices in K are connected. In this paper, we present a linear-time algorithm for finding the most vital edge with respect to K-terminal reliability in series-parallel networks.
PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE
(1992)
HSU, LH
;
WANG, PF
;
WU, CT
;
資訊工程學系
;
Department of Computer Science
Given a weighted graph G, the weight of a spanning tree T, denoted by w(T), is defined as the total weight of all edges in T. A spanning tree T in G is called a minimum spanning tree if w(T) less-than-or-equal-to w(T') for all spanning trees T' in G. Let w(G) denote the weight of the minimum spanning tree of G if G is connected; otherwise, w(G) = infinity. An edge e is called a most vital edge in G if w(G - e) greater-than-or-equal-to w(G - e') for every edge e' of G where G - e' denotes the partial graph obtained by removing e' from G. In this paper, we present several cost-optimal parallel algorithms, under different computation models, to find the most vital edge in a weighted graph.
PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE
(1992-01-01)
HSU, LH
;
WANG, PF
;
WU, CT
;
資訊工程學系
;
Department of Computer Science
PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE
(1992-01-01)
HSU, LH
;
WANG, PF
;
WU, CT
;
資訊工程學系
;
Department of Computer Science
The weight of a weighted graph G, w(G), is defined to be the weight of its minimum spanning tree. An edge e is called a most vital edge in G if w(G - e) greater-than-or-equal-to w(G - e') for every edge e' of G. In this paper, we present several cost-optimal parallel algorithms, under different computation models, to find the most vital edge in a weighted graph.
PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE
(1992)
HSU, LH
;
WANG, PF
;
WU, CT
;
資訊工程學系
;
Department of Computer Science
The weight of a weighted graph G, w(G), is defined to be the weight of its minimum spanning tree. An edge e is called a most vital edge in G if w(G - e) greater-than-or-equal-to w(G - e') for every edge e' of G. In this paper, we present several cost-optimal parallel algorithms, under different computation models, to find the most vital edge in a weighted graph.