Research Article
Generation of All Spanning Trees in the Limelight
@INPROCEEDINGS{10.1007/978-3-642-27317-9_20, author={Saptarshi Naskar and Krishnendu Basuli and Samar Sarma}, title={Generation of All Spanning Trees in the Limelight}, proceedings={Advances in Computer Science and Information Technology. Computer Science and Information Technology. Second International Conference, CCSIT 2012, Bangalore, India, January 2-4, 2012. Proceedings, Part III}, proceedings_a={CCSIT PART III}, year={2012}, month={11}, keywords={Spanning Tree Vertex Connectivity KMTT PRIES SPRIES}, doi={10.1007/978-3-642-27317-9_20} }- Saptarshi Naskar
Krishnendu Basuli
Samar Sarma
Year: 2012
Generation of All Spanning Trees in the Limelight
CCSIT PART III
Springer
DOI: 10.1007/978-3-642-27317-9_20
Abstract
Many problems in science and engineering [1, 3, 8, 10] can be formulated in terms of graphs. There are problems where spanning trees are necessary to be computed from the given graphs. Connected subgraph with all the vertices of the graph (V,E), where |V|=, having exactly of (1 edges called the spanning tree of the given graph. The major bottleneck of any tree generation algorithm is the prohibitively large cost of testing whether a newly born tree is twin of a previously generated one and also there is a problem that without checking for circuit generated subgraph is tree or non-tree. This problem increases the time complexity of the existing algorithms. The present approach avoids this problem with a simple but efficient procedure and at the same time ensures that a large number of non-tree subgraphs are not generated at all.