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: 2014-02-28
Authors : Sang-Un Lee; Myeong-Bok Choi;
Page : 51-59
Keywords : Minimum Spanning Tree; Valency; Edges Population; Stopping Criteria;
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.
Other Latest Articles
- An Establishment of the Process System for Software Requirements Engineering
- Optimum Design of the Microphone Sensor Array for 3D TDOA Positioning System
- Implementation of Indoor Navigation System using VLC based-Smart Devices
- Reliability Improvement of the Tag Bits of the Cache Memory against the Soft Errors
- Design of Waveguide Low Pass Filter using Rectangular Rings and Ridges
Last modified: 2016-01-29 13:21:36