Abstrait

GÉNÉRATION DE TOUS LES ARBRES COUVERTS UNE APPROCHE COMBINATOIRE

Saptarshi Naskar, Krishnendu Basuli et Samar Sen Sarma

Cet article traite de la génération de tous les arbres de recouvrement d'un graphe simple, symétrique et connexe. Étant donné que le nombre d'arbres de recouvrement d'un graphe est asymptotiquement exponentiel, nous nous efforçons de générer tous les arbres dans un laps de temps et d'espace raisonnables[1]. La méthode ici est qualitativement et quantitativement meilleure que les méthodes existantes. La raison derrière cette affirmation est le nombre minimum de comparaisons d'arbres dupliqués et l'absence de test de circuit pour sa réalisation[1,6-11]. Nous espérons que l'amélioration de l'algorithme réside dans l'objectif de ne générer aucun arbre dupliqué.