On the problem of finding all minimum spanning trees
João Martinez, Rosiane de Freitas, Altigran da Silva · Matemática Contemporânea · 2017
A minimum spanning tree is a subgraph of an undirected weighted graph that still connects all the vertices, has no cycles and has minimum total weight.Many efficient algorithms are known to solve the problem of determining a single best solution to the problem, such as Prim's and Kruskal's algorithms.However, the problem of enumerating all the minimum spanning trees of a graph is an NPhard problem, it has great theoretical and practical importance, but there are few algorithms to solve it.In this work, we analyze these algorithms and their properties and we make a comparison with the use of experiments.Such algorithms were analyzed according to their theoretical properties, computational complexity and implementation details, and a comparative analysis was performed using general and specific graph class instances.