Questions tagged [spanning-tree]

The tag has no usage guidance.

4 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
169 views

How to sample a lot of independent uniform spanning trees?

There are a bunch of good algorithms for sampling a uniform spanning tree from a graph $G$. For example, Aldous/Broder and Wilson's algorithm are pretty efficient. However, each of these graphs only ...
5
votes
0answers
68 views

Enumerating homologies of disjoint paths

I am reading this recent paper by Schrijver, in particular, section 4.2: Enumerating homologies of disjoint paths. I did not understand how do they re-route the paths through a spanning tree and ...
4
votes
0answers
147 views

Girth of graphs that decompose into two disjoint union of spanning trees

Let $G$ be an $n$-node graph that can be decomposed into two disjoint union of spanning trees. In particular, $G$ has $2n-2$ edges. It is not hard to show that the girth of $G$ is at most $O(\log n)...
2
votes
0answers
75 views

Variation of edge-disjoint spanning trees

In a directed graph, I want to find 2 edge-disjoint spanning trees (arborescence), with the extra restrictions that edges in the 1st tree are not forward arcs in the 2nd tree. Are there existing ...