Абстрактный

GENERATION OF ALL SPANNING TREES A COMBINATORIAL APPROACH

Saptarshi Naskar, Krishnendu Basuli and Samar Sen Sarma

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.