標題: 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
顯示於類別:期刊論文