ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Fast Determination of Minimum Spanning Tree Based on Down-sizing Technique of Edges Population

Journal: The Journal of the Institute of Internet, Broadcasting and Communication (Vol.14, No. 1)

Publication Date:

Authors : ; ;

Page : 51-59

Keywords : Minimum Spanning Tree; Valency; Edges Population; Stopping Criteria;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

This paper suggests a method of lessening number of a graph's edges population in order to rapidly obtain the minimum spanning tree. The present minimum spanning tree algorithm works on all the edges of the graph. However, the suggested algorithm reduces the edges population size by means of applying a method of deleting maximum weight edges in advance from vertices with more than 2 valencies. Next, it applies a stopping criterion which ideally terminates Borůvka, Prim, Kruskal and Reverse-Delete algorithms for reduced edges population. On applying the suggested algorithm to 9 graphs, it was able to minimize averagely 83% of the edges that do not become MST. In addition, comparing to the original graph, edges are turned out to be lessened 38% by Borůvka, 37% by Prim, 39% by Kruskal and 73% by Reverse-Delete algorithm, and thereby the minimum spanning tree is obtained promptly.

Last modified: 2016-01-29 13:21:36