Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What do you mean by "anchored at each vertex"? Any spanning tree will use each vertex. – utdiscant Feb 3 '14 at 22:05

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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