Ask Your Question

Time/Space Requirements of Graph.spanning_trees()

asked 2020-09-17 08:27:11 +0200

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 10:19:39 +0200 )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-18 05:39:43 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2020-09-17 10:01:15 +0200

slelievre gravatar image

updated 2020-09-30 14:05:41 +0200

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 or later 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 08:27:11 +0200

Seen: 200 times

Last updated: Sep 30 '20