A Divide-and-Conquer Algorithm for All Spanning Tree Generation

摘要

This paper claims to propose a unique solution to the problem of all possible spanning tree enumeration for a simple, symmetric, and connected graph. It is based on the algorithmic paradigm named divide-and-conquer. Our algorithm proposes to perform no duplicate tree comparison and a minimum number of circuit testing, consuming reasonable time and space.