Research Article
A Study on ‘Number of Spanning Trees’
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 73 - Issue 19 |
| Published: July 2013 |
| Authors: Adarsh Kumar Verma, Saurabh Sharma, Anuj Tiwari |
10.5120/12994-0250
|
Adarsh Kumar Verma, Saurabh Sharma, Anuj Tiwari . A Study on ‘Number of Spanning Trees’. International Journal of Computer Applications. 73, 19 (July 2013), 27-31. DOI=10.5120/12994-0250
@article{ 10.5120/12994-0250,
author = { Adarsh Kumar Verma,Saurabh Sharma,Anuj Tiwari },
title = { A Study on ‘Number of Spanning Trees’ },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 73 },
number = { 19 },
pages = { 27-31 },
doi = { 10.5120/12994-0250 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Adarsh Kumar Verma
%A Saurabh Sharma
%A Anuj Tiwari
%T A Study on ‘Number of Spanning Trees’%T
%J International Journal of Computer Applications
%V 73
%N 19
%P 27-31
%R 10.5120/12994-0250
%I Foundation of Computer Science (FCS), NY, USA
Abstract
There exist many algorithms for producing the spanning trees of a graph with better time and space complexities. In this research study, we are presenting a study on number of spanning trees and a technique based on the basic cycle to find the number of spanning trees and also the structure of all the spanning trees of a labeled and undirected graph.
References
- Char, J. P. , Generation of Trees, Two-Trees and Storage of Master Forests, IEEE Transactions on Circuit Theory, Vol. CT-15, pp. 128-138, 1968.
- Hakimi, S. L. , On Trees of a Graph and their Generation, Journal of the Franklin Institute, Vol. 272, No. 5, pp. 347-359, 1961.
- Kapoor, S. and H. Ramesh, Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs, SIAM Journal on Computing, Vol. 24, No. 2, 1995.
- Matsui, T. , An Algorithm for Finding All the Spanning Trees in Undirected Graphs, Technical Report: METR 93-08, Department of Mathematical Engineering and Information Physics, University of Tokyo, Tokyo, 1993.
- Mayeda, W. and S. Seshu, Generation of Trees without Duplications, IEEE Transactions on Circuit Theory, Vol. CT-12, pp. 181-185, 1965.
- Minty, G. J. , A Simple Algorithm for Listing All the Trees of a Graph, IEEE Transactions on Circuit Theory, Vol. CT-12, pp. 120, 1965.
- Sen Sarma, S. , A. Rakshit, R. K. Sen, and A. K. Choudhury, An Efficient Tree Generation Algorithm, Journal of the Institution of Electronics and Telecommunications Engineers, Vol. 27, No. 3, pp. 105-109, 1981.
- Shioura, A. and A. Tamura, Efficiently Scanning All Spanning Trees of an Undirected Graph, Research Report: B-270, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, 1993.
- Winter, P. , An Algorithm for the Enumeration of Spanning Trees, BIT, Vol. 26, pp. 44-62, 1986.
Index Terms
Keywords