Ask Your Question

Time/Space Requirements of Graph.spanning_trees()

asked 2020-09-17 01:27:11 -0500

BurnsidesLlama gravatar image

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.

edit retag flag offensive close merge delete


Just a side suggestion regarding your problem: you should try use the symmetries of the dodecahedron to avoid useless work when iterating over suc large objects.

tmonteil gravatar imagetmonteil ( 2020-09-17 03:19:39 -0500 )edit

@tmonteil I had a similar thought using symmetries, where we somehow find representatives of each orbit of spanning trees (in the sense of the symmetries of the dodecahedron as a group action on the set of spanning trees), and somehow find the size of each orbit. I don't know how to do this efficiently though, as it seems I need to consider every spanning tree before I can find a representative of each orbit.

BurnsidesLlama gravatar imageBurnsidesLlama ( 2020-09-17 22:39:43 -0500 )edit

1 answer

Sort by ยป oldest newest most voted

answered 2020-09-17 03:01:15 -0500

slelievre gravatar image

Making the spanning_trees method return an iterator rather than a list is the object of

which was merged in Sage 9.2.beta12.

Install Sage 9.2.beta12 to try it out.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2020-09-17 01:27:11 -0500

Seen: 23 times

Last updated: Sep 17