Spanning Tree- Properties, Algorithms and Applications
DOI:
https://doi.org/10.26438/ijcse/v5i10.5458Keywords:
Graph, Spanning Tree, Minimum Spanning TreeAbstract
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.
References
Alexander K. Kelmans., On graphs with the maximum number of spanning trees 1996.
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.
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
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
Chen , W. K., On directed trees and directed k-trees of a digraph and their generation, SIAM J. Appl. Math. 14 550–560, 1966
Das et al., The number of spanning trees of a graph, Journal of Inequalities and Applications, 2013.
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.
Gabow, H.N., Two algorithms for generating weighted spanning trees in order. SIAM Journal on Computing, 6(1), 139-150., 1977.
Gabow, H.N. & Myers, E.W., Finding all spanning trees of directed and undirected graphs. SIAM Journal on Computing, 7, 280-287. 1978.
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
Kapoor, S. & Ramesh, H., Algorithms for enumerating all spanning trees of undirected and weighted graphs. SIAM Journal on Computing, 24, 247-265.,1995
Kapoor, S. & Ramesh, H. An algorithm for enumerating all spanning trees of a directed graph. Algorithmica, 27(2), 120-130.,1997.
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.
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.
Matsui, T., A flexible algorithm for generating all the spanning trees in undirected graphs. Algorithmica, 18(4), 530-543., 1997.
Matsui, Tomomi., An Algorithm for Finding All the Spanning Trees in Undirected Graphs., 1998.
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.
Minty, G.J., A simple algorithm for listing all the trees of a graph. IEEE Transactions on Circuit Theory, CT-12, 120, 1975.
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.
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.
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.
Winter, Pawel,. An Algorithm for the Enumeration of Spanning Trees.. BIT. 26. 44-62. 10.1007/BF01939361.1985.
Wu, Bang Ye; Chao, Kun-Mao , Spanning Trees and Optimization Problems, CRC Press, ISBN 1-58488-436-3,2004.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
