Open Access   Article

Spanning Tree- Properties, Algorithms and Applications

K. Lakshmi1 , T. Meyyappan2

1 Department of MCA, Sir M Visvesvaraya Institute of Technology, Bangalore, India.
2 Department of Computer Science and Engineering, Alagappa University, Karaikudi, India.

Correspondence should be addressed to:

Section:Research Paper, Product Type: Journal Paper
Volume-5 , Issue-10 , Page no. 54-58, Oct-2017


Online published on Oct 30, 2017

Copyright © K. Lakshmi, T. Meyyappan . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library


IEEE Style Citation: K. Lakshmi, T. Meyyappan, “Spanning Tree- Properties, Algorithms and Applications”, International Journal of Computer Sciences and Engineering, Vol.5, Issue.10, pp.54-58, 2017.

MLA Style Citation: K. Lakshmi, T. Meyyappan "Spanning Tree- Properties, Algorithms and Applications." International Journal of Computer Sciences and Engineering 5.10 (2017): 54-58.

APA Style Citation: K. Lakshmi, T. Meyyappan, (2017). Spanning Tree- Properties, Algorithms and Applications. International Journal of Computer Sciences and Engineering, 5(10), 54-58.

238 183 downloads 139 downloads


In this paper, we present a survey of the spanning trees. The general properties of spanning trees, algorithms for generation of all possible spanning trees from a graph and minimum spanning tree algorithms are discussed in this paper. The purpose of this study is to give fundamental details on the spanning trees and related work done based on their application domains. The application domains include computer networks, bio-informatics, image processing etc. It is found that research related to spanning trees can be related to the area of graph mining.

Key-Words / Index Term

Graph, Spanning Tree, Minimum Spanning Tree


[1] Alexander K. Kelmans., On graphs with the maximum number of spanning trees 1996.
[2] AR. PonPeriasamy , E. Thenmozhi, A Brief survey of Data Mining Techniques Applied to Agricultural Data, International Journal of Computer Sciences and Engineering, 4(5), 2017.
[3] Burcu Bozkurt and Durmuş Bozkurt, “On the Number of Spanning Trees of Graphs,” The Scientific World Journal, Vol. 2014, Article ID 294038, 5 pages, 2014. doi:10.1155/2014/294038
[4] Chakraborty, Maumita & Hazra, Goutam & Pal, Rajat, Divide-and-Conquer: An Approach to Generate All Spanning Trees of a Connected and Undirected Simple Graph. 700-91,2017
[5] Chen , W. K., On directed trees and directed k-trees of a digraph and their generation, SIAM J. Appl. Math. 14 550–560, 1966
[6] Das et al., The number of spanning trees of a graph, Journal of Inequalities and Applications, 2013.
[7] Dr. T. Karthikeyan, S. John Peter, B. Praburaj (2012) Minimum Spanning Tree-based Clustering Applied to Protein Sequences in Early Cancer Diagnosis, International Journal of Computer Science And Technology, Vol. 3, Issue 1, Jan. - March 2012.
[8] Gabow, H.N., Two algorithms for generating weighted spanning trees in order. SIAM Journal on Computing, 6(1), 139-150., 1977.
[9] Gabow, H.N. & Myers, E.W., Finding all spanning trees of directed and undirected graphs. SIAM Journal on Computing, 7, 280-287. 1978.
[10] Hakimi, S.L., On trees of a graph and their generation. Journal of the Franklin Institute. 272. 347-359. 10.1016/0016-0032(61)90036-9.,1961
[11] Kapoor, S. & Ramesh, H., Algorithms for enumerating all spanning trees of undirected and weighted graphs. SIAM Journal on Computing, 24, 247-265.,1995
[12] Kapoor, S. & Ramesh, H. An algorithm for enumerating all spanning trees of a directed graph. Algorithmica, 27(2), 120-130.,1997.
[13] Kocay, William; Kreher, Donald L., "5.8 The matrix-tree
theorem", Graphs, Algorithms, and Optimization, Discrete Mathematics and Its Applications, CRC Press, pp. 111–116, ISBN 978-0-203-48905-5., 2004.
[14] Matsui, An algorithm for finding all the spanning trees in undirected graphs. Technical Report METR 93-08, Dept. of Mathematical Engineering and Information Physics, University of Tokyo, Tokyo, 1993.
[15] Matsui, T., A flexible algorithm for generating all the spanning trees in undirected graphs. Algorithmica, 18(4), 530-543., 1997.
[16] Matsui, Tomomi., An Algorithm for Finding All the Spanning Trees in Undirected Graphs., 1998.
[17] McDiarmid, Colin; Johnson, Theodore; Stone, Harold S., "On finding a minimum spanning tree in a network with random weights" , Random Structures & Algorithms, 10 (1-2): 187–204, MR 1611522.,1997.
[18] Minty, G.J., A simple algorithm for listing all the trees of a graph. IEEE Transactions on Circuit Theory, CT-12, 120, 1975.
[19] Naskar S., Basuli K., Sarma S.S., Generation of All Spanning Trees in the Limelight. In: Meghanathan N., Chaki N., Nagamalai D. (eds) Advances in Computer Science and Information Technology. Computer Science and Information Technology. CCSIT 2012.
[20] Shioura, A. & Tamura, A, . Efficiently scanning all spanning trees of an undirected graph. Journal of the Operations Research Society of Japan, 38(3), 331-344., 1995.
[21] S. Joshi , F.U. Khan , N. Thakur., Contrasting and Evaluating Different Clustering Algorithms: A Literature Review.,International Journal of Computer Sciences and Engineering., Volume-2 , Issue-4 , Page no. 87-91, Apr-2014.
[22] Winter, Pawel,. An Algorithm for the Enumeration of Spanning Trees.. BIT. 26. 44-62. 10.1007/BF01939361.1985.
[23] Wu, Bang Ye; Chao, Kun-Mao , Spanning Trees and Optimization Problems, CRC Press, ISBN 1-58488-436-3,2004.