Ask Your Question

Revision history [back]

Time/Space Requirements of Graph.spanning_trees()

Hello, I'm working on finding the number of a certain kind of spanning tree of a graph, and doing the Dodecahedron graph as an example. My naive algorithm for doing this iterates through all of its 5000000 or so spanning trees and runs a linear time (in graph size) algorithm on each spanning tree. The size of this problem seems just possible with my home computer, but Sage's builtin Graph.spanning_trees() is using too much RAM. Beyond this, I am unsure if the running time is reasonable once the RAM problem is fixed.

Do you know where I can find documentation discussing the implementation of this function? I imagine there could be a lazy version of this algorithm that makes the problem reasonable.