PRIM’S MINIMUM COST SPANNING TREE THEORY

Mohamed Faidz Mohamed Said #1

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 faidzms@ieee.org 


 
Abstract— This paper states the theory of the Prim’s algorithm starting with the history of this algorithm. Then this paper provides an example of Prim’s algorithm for a better understanding of this algorithm and minimum cost spanning tree. Beside that a few applications which were done by other researchers are included in this paper.
Keywords: Prim’s algorithm, minimum cost spanning tree



REFERENCES

[1].	Foulds L.F., Graph theory application, Springer-Verlag, New York, J. Clerk Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon, 1892, pp.68–73, 1992.

[2].	Graham R. L and Hell P., On the history of the minimum spanning tree problem, annals of the history of computing 7: 43-57, 1985.

[3].	J. B. Kruskal. On the shortest spanning subtree and the traveling salesman problem. Proc. Am. Math. Soc., 7:48.50, 1956.

[4].	R. C. Prim. Shortest connection and some generalizations. Bell Syst. Tech. J., 36, 1957.

[5].	Wei Wang, Yongzhong Huang, Shaozhong Guo, “Design and Implementation of GPUBased Prim's Algorithm”, I.J.Modern Education and Computer Science, 2011.

[6].	R. Setia, A. Nedunchezhian, and S. Balachandran, "A new parallel algorithm for minimum spanning tree problem," Proc.International Conference on High Performance Computing (HiPC), pp. 1-5, 2009.

[7].	E. Gonina and L. Kalé, "Parallel Prim’s algorithm on dense graphs with a novel extension," Tech. Rep., 2007.

[8].	D. A. Bader and G. Cong, "Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs," Journal of Parallel and Distributed Computing, v.66 n.11, p.1366-1378, November 2006.

[9].	G. Karypis, A. Grama, A. Gupta and V. Kumar. Introduction to Parallel Computing. Addison Weslesy, second edition, 2003.

[10].	Vineet, P. Harish, S. Patidar, and P. J. Narayanan, "Fast minimum spanning tree for large graphs on the GPU, " in HPG ’09: Proceedings of the Conference on High Performance Graphics, pp. 167– 171, 2009.

[11].	T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT press, 2001.

[12].	Leist, D. P. Playne and K. A. Hawick. "Exploiting graphical processing units for data-parallel scientific applications".Tech. Rep., December, 2009.

[13].	O. T. Arogundade, B. Sobowale, and A. T. Akinwale, Prim Algorithm Approach to Improving Local Access Network in Rural Areas, International Journal of Computer Theory and Engineering, Vol. 3, No. 3, June 2011.

[14].	N. Jain, P. S. Shivalkar, N. Jainsankar, Distance Calculator Using Prim’s Algorithm, The International Journal of Computer Science & Applications (TIJCSA), Volume 2, No. 03, May 2011.