GENERATION OF ALL SPANNING TREES A COMBINATORIAL APPROACH | Abstract

ISSN: 2229-371X

Research Article Open Access

GENERATION OF ALL SPANNING TREES A COMBINATORIAL APPROACH

Abstract

This paper deals with all spanning tree generation of a simple, symmetric and connected graph. Since, number of spanning trees of a graph is asymptotically exponential it is our endeavor to generate, all trees in reasonable amount of time and space[1]. The method here is qualitatively and quantitatively better than existing methods. The reason behind the claim is minimum number of duplicate tree comparison and no circuit testing at all for its realization[1,6-11]. We are hopeful that betterment of the algorithm lies in the target of no duplicate tree generation.

Saptarshi Naskar, Krishnendu Basuli and Samar Sen Sarma

To read the full article Download Full Article