Sang Un Lee

The KIPS Transactions:PartA, Vol. 17, No. 3, pp. 159-166, Jun. 2010
10.3745/KIPSTA.2010.17.3.159,   PDF Download:

Abstract

In this paper, to obtain the Minimum Spanning Tree (MST) from the graph with several nodes having the same weight, I applied both Bor?vka and Kruskal MST algorithms. The result came out to such a way that Kruskal MST algorithm succeeded to obtain MST, but not did the Prim MST algorithm. It is also found that an algorithm that chooses Inter-MSF MWE in the 2nd stage of Bor?vka is quite complicating. The 1st stage of Bor?vka has an advantage of obtaining Minimum Spanning Forest (MSF) with the least number of the edges, and on the other hand, Kruskal MST algorithm has an advantage of always obtaining MST though it deals with all the edges. Therefore, this paper suggests an Hybrid MST algorithm which consists of the merits of both Bor?vka's 1st stage and Kruskal MST algorithm. When applied additionally to 6 graphs, Hybrid MST algorithm has a same effect as that of Kruskal MST algorithm. Also, comparing the algorithm performance speed and capacity, Hybrid MST algorithm has shown the greatest performance Therefore, the suggested algorithm can be used as the generalized MST algorithm.

Statistics
Cite this article