Browsing by Author "WU, CT"

Now showing 1 - 4 of 4

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.