1
$\begingroup$

I have a strongly connected directed graph with about 10 vertices and 20 edges, and would like to find all spanning trees anchored at each vertex. Is there a systematic way, or a tested program/algorithm that would help me find all these spanning trees?

When I was looking at graphs with a smaller number of vertices and edges, I could simply write the spanning trees at each vertex out, but this gets more cumbersome when the graph gets bigger. Thanks in advance for your suggestions.

$\endgroup$
  • $\begingroup$ What do you mean by "anchored at each vertex"? Any spanning tree will use each vertex. $\endgroup$ – utdiscant Feb 3 '14 at 22:05
1
$\begingroup$

I think the paper by Takeaki Uno, An algorithm for enumerating all directed spanning trees in a directed graph, should help you solve your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.