People who code: we want your input. Take the Survey

Questions tagged [spanning-tree]

The tag has no usage guidance.

5 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
201 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 ...
6
votes
0answers
106 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
157 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
78 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 ...
0
votes
0answers
27 views

Finding the smallest-cost way to deliver goods

I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each ...