Sanjay Kumar Pal; Samar Sen Sarma

International Journal of Information Technology and Computer Science (IJITCS)

IJITCS Vol. 5, No. 9, 8 Aug. 2013

Cover page and Table of Contents: PDF (size: 312KB)

An Approach of Degree Constraint MST Algorithm

Full Text (PDF, 312KB), PP.80-86

Views: 0 Downloads: 0

Author(s)

Sanjay Kumar Pal ^1,* Samar Sen Sarma ²

1. Department of Computer Sc. and Applications, NSHM College of Management and Technology, Kolkata, India

2. Department of Computer Science and Engineering, University of Calcutta, Kolkata, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2013.09.08

Received: 20 Sep. 2012 / Revised: 16 Feb. 2013 / Accepted: 10 May 2013 / Published: 8 Aug. 2013

Index Terms

Graph, Tree, Minimal Spanning Tree, Algorithm, Average Degree Sequence

Abstract

This paper is approaching a new technique of creating Minimal Spanning Trees based on degree constraints of a simple symmetric and connected graph G. Here we recommend a new algorithm based on the average degree sequence factor of the nodes in the graph. The time complexity of the problem is less than O(N log|E|) compared to the other existing time complexity algorithms is O(|E| log|E|)+C of Kruskal, which is optimum. The goal is to design an algorithm that is simple, graceful, resourceful, easy to understand, and applicable in various fields starting from constraint based network design, mobile computing to other field of science and engineering.

Cite This Paper

Sanjay Kumar Pal, Samar Sen Sarma, "An Approach of Degree Constraint MST Algorithm", International Journal of Information Technology and Computer Science(IJITCS), vol.5, no.9, pp.80-86, 2013. DOI:10.5815/ijitcs.2013.09.08

Reference

[1]N. Deo, “Graph Theory with Application to Engineering and Computer Sciences,” PHI, Englewood Cliffs, N. J., 2007.

[2]Thomas H. Coremen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, PHI, Second Edition, 2008.

[3]Harowitz Sahnai & Rajsekaran, “Fundamentals of Computer Algorithms”,Galgotia Publications Pvt. Ltd., 2000.

[4]J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications”, The Macmillan Press, Great Britain, 1976

[5]http://en.wikipedia.org/wiki/Boruvka’s_algorithm, 28 November 2012.

[6]http://en.wikipedia.org/wiki/Degree_(graph_theory), 24 September 2012.

[7]anjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, “Algorithms”, Tata McGraw-Hill, First Edition, 2008.

[8]A. Rakshit, A. K. Choudhury, S. S. Sarma and R.K. Sen, “An Efficient Tree Generation Algorithm,” IETE, vol. 27, pp. 105-109, 1981.

[9]Sanjay Kumar Pal and Samar Sen Sarma, “An Efficient All Spanning Tree Generation Algorithm”, IJCS, vol. 2, No. 1, pp. 48 – 59, January 2008.

[10]F. A. Muntaner-Batle and M. Rius Font, “A Note on degree Sequence of Graphs with restrictions”, http://upcommons.upc.edu/eprints/bitstream/2117/1490/1/sequences.pdf, 02 January 2013.

[11]Arumugam S. and Ramachandran S., Invitation to Graph Theory, Scitech Publications(INDIA) Pvt. Ltd., Chennai, 2002.