Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | HSU, LH | en_US |
dc.contributor.author | WANG, PF | en_US |
dc.contributor.author | WU, CT | en_US |
dc.date.accessioned | 2014-12-08T15:04:47Z | - |
dc.date.available | 2014-12-08T15:04:47Z | - |
dc.date.issued | 1992 | en_US |
dc.identifier.issn | 0167-8191 | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/3286 | - |
dc.description.abstract | 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. | en_US |
dc.language.iso | en_US | en_US |
dc.subject | WEIGHTED GRAPHS | en_US |
dc.subject | MINIMUM SPANNING TREE | en_US |
dc.subject | COMPUTATION MODELS | en_US |
dc.subject | VITAL EDGE | en_US |
dc.subject | COST-OPTIMAL PARALLEL ALGORITHMS | en_US |
dc.title | PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE | en_US |
dc.type | Article | en_US |
dc.identifier.journal | PARALLEL COMPUTING | en_US |
dc.citation.volume | 18 | en_US |
dc.citation.issue | 10 | en_US |
dc.citation.spage | 1143 | en_US |
dc.citation.epage | 1155 | en_US |
dc.contributor.department | 資訊工程學系 | zh_TW |
dc.contributor.department | Department of Computer Science | en_US |
dc.identifier.wosnumber | WOS:A1992JZ65500004 | - |
dc.citation.woscount | 12 | - |
Appears in Collections: | Articles |