標題: | PARALLEL ALGORITHMS FOR FINDING THE MOST VITAL EDGE WITH RESPECT TO MINIMUM SPANNING TREE |
作者: | HSU, LH WANG, PF WU, CT 資訊工程學系 Department of Computer Science |
關鍵字: | WEIGHTED GRAPHS;MINIMUM SPANNING TREE;COMPUTATION MODELS;VITAL EDGE;COST-OPTIMAL PARALLEL ALGORITHMS |
公開日期: | 1992 |
摘要: | 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. |
URI: | http://hdl.handle.net/11536/3596 |
ISSN: | 0926-5473 |
期刊: | IFIP TRANSACTIONS A-COMPUTER SCIENCE AND TECHNOLOGY |
Volume: | 12 |
起始頁: | 284 |
結束頁: | 290 |
顯示於類別: | 期刊論文 |