UNDERSTANDING THE SIMPLE DEVELOPMENT PROCESS OF KRUSKAL’S MINIMUM SPANNING TREE ALGORITHM
 
Nurul Intan Qodreah Sanusi #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 n.intanqodreah@gmail.com
2 faidzms@ieee.org

 
Abstract—The basic idea of Kruskal’s algorithm is to scan involved edge on increasing weight command. Since this algorithm is popular to solve real world problem, many students need to explore this minimum spanning tree (MST) to apply the suitable real-world problem regarding to their studies. The main purpose of this paper is to brief the basic idea of Kruskal’s algorithm for fresh researcher or forecaster that are new to Kruskal’s MST. In this paper, graph theory will be used to recognize this Kruskal’s algorithm. With the basic idea, step to use Kruskal’s algorithm is shown in the implementation of this algorithm by using real world popular situation, Chinese Postman Problem.
Keywords: Kruskal’s algorithm, MST, Prim, HCPP



REFERENCES

[1] 	RGraham, P., On the history of minimum spanning tree problem. IEEE Annals of the History of Computing, 1985. 7(1): p. 43-57.

[2] 	Hsu, L.-H., et al., Finding the most vital edge with respect to minimum spanning tree in weighted graphs. Information Processing Letters, 1991. 39(5): p. 277-281.

[3] 	Lorenzo, L. and S. Lorenzo-Freire, A characterization of Kruskal sharing rules for minimum cost spanning tree problems. International Journal of Game Theory, 2008. 38(1): p. 107-126.

[4] 	Berger, R., S. Dubuisson, and C. Gonzales. Fast multiple histogram computation using Kruskal's algorithm. in 2012 19th IEEE International Conference on Image Processing. 2012.

[5] 	Sayata, U.B. and N.P. Desai. An algorithm for Hierarchical Chinese postman problem using minimum spanning tree approach based on Kruskal's algorithm. in Advance Computing Conference (IACC), 2015 IEEE International. 2015.

[6] 	Korteweg, P., Postman Problems, Priorities and the Concept of Servicing. Salamanca, 2002.

[7] 	Sörensen, K. and G.K. Janssens, An algorithm to generate all spanning trees of a graph in order of increasing cost. Pesquisa Operacional, 2005. 25: p. 219-229.

[8] 	Panayiotopoulos, J.-C., Probabilistic analysis of solving the assignment problem for the traveling salesman problem. European Journal of Operational Research, 1982. 9(1): p. 77-82.

[9] 	Guttoski, P.B., M.S. Sunye, and F. Silva. Kruskal's Algorithm for Query Tree Optimization. in Database Engineering and Applications Symposium, 2007. IDEAS 2007. 11th International. 2007.

[10] 	Katajainen, J. and O. Nevalainen, An alternative for the implementation of Kruskal's minimal spanning tree algorithm. Science of Computer Programming, 1983. 3(2): p. 205-216.

[11] 	Horowitz, E. and S. Sahni, Fundamentals of data structures. 1983, Pitman.

[12] 	Djauhari, M.A. and S.L. Gan, Minimal spanning tree problem in stock networks analysis: An efficient algorithm. Physica A: Statistical Mechanics and its Applications, 2013. 392(9): p. 2226-2234.

[13] 	Greenberg, H.J., Greedy algorithms for minimum spanning tree. University of Colorado at Denver, 1998.

[14] 	Greistorfer, P., A Tabu Scatter Search Metaheuristic for the Arc Routing Problem. Computers & Industrial Engineering, 2003. 44(2): p. 249-266.

[15] 	Kruskal, J.B., On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 1956. 7(1): p. 48-50.

[16] 	Santos, L., J. Coutinho-Rodrigues, and J.R. Current, Implementing a multi-vehicle multi-route spatial decision support system for efficient trash collection in Portugal. Transportation Research Part A: Policy and Practice, 2008. 42(6): p. 922-934.