An Approach of Degree Constraint MST Algorithm
Автор: Sanjay Kumar Pal, Samar Sen Sarma
Журнал: International Journal of Information Technology and Computer Science(IJITCS) @ijitcs
Статья в выпуске: 9 Vol. 5, 2013 года.
Бесплатный доступ
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.
Graph, Tree, Minimal Spanning Tree, Algorithm, Average Degree Sequence
Короткий адрес: https://sciup.org/15011967
IDR: 15011967
Список литературы An Approach of Degree Constraint MST Algorithm
- N. Deo, “Graph Theory with Application to Engineering and Computer Sciences,” PHI, Englewood Cliffs, N. J., 2007.
- Thomas H. Coremen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, PHI, Second Edition, 2008.
- Harowitz Sahnai & Rajsekaran, “Fundamentals of Computer Algorithms”,Galgotia Publications Pvt. Ltd., 2000.
- J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications”, The Macmillan Press, Great Britain, 1976
- http://en.wikipedia.org/wiki/Boruvka’s_algorithm, 28 November 2012.
- http://en.wikipedia.org/wiki/Degree_(graph_theory), 24 September 2012.
- anjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, “Algorithms”, Tata McGraw-Hill, First Edition, 2008.
- A. Rakshit, A. K. Choudhury, S. S. Sarma and R.K. Sen, “An Efficient Tree Generation Algorithm,” IETE, vol. 27, pp. 105-109, 1981.
- Sanjay Kumar Pal and Samar Sen Sarma, “An Efficient All Spanning Tree Generation Algorithm”, IJCS, vol. 2, No. 1, pp. 48 – 59, January 2008.
- 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.
- Arumugam S. and Ramachandran S., Invitation to Graph Theory, Scitech Publications(INDIA) Pvt. Ltd., Chennai, 2002.
