Questions tagged [spanning-trees]
The spanning tree of a connected undirected graph G is a tree having all the vertices and some number of edges of G.
23
questions with no upvoted or accepted answers
8
votes
0
answers
186
views
MST with possibly minimal diameter
I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
6
votes
0
answers
774
views
Minimum vertex-weight directed spanning tree where the weight function depends on the tree
Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$.
The weight function assigns a non-...
- 61
5
votes
0
answers
167
views
MST that contains a shortest $s,t$-path
Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$...
4
votes
1
answer
137
views
Survival algorithm for Network deterministic failures
Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
- 41
3
votes
0
answers
4k
views
Applications of min spanning trees
What are the significant applications of minimum spanning trees?
After doing some research online and in several textbooks, I have found three real-world applications:
Building a connected network. ...
D.W.♦
- 152k
2
votes
0
answers
36
views
The Roskind-Tarjan Algorithm
I am going through the paper https://pubsonline.informs.org/doi/abs/10.1287/moor.10.4.701 which is
A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees and the authors are James Roskind and ...
- 53
2
votes
0
answers
47
views
Edmond's theorem for k-disjoint arborescences in digraphs
Recently while studying arborescences in graph theory, I came across Edmond's theorem for $k$ edge-disjoint arborescences in digraphs
if a finite digraph is $k$ edge-connected from a vertex r for ...
- 53
2
votes
0
answers
63
views
Total weight of all spanning trees
Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
- 141
1
vote
1
answer
186
views
Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree
CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have
...
- 818
1
vote
0
answers
216
views
Form a Tree having minimum diameter
I am given a connected graph. I have to construct a spanning tree from the graph, that has minimum diameter.
However, I looked for the solution, and the solution goes like this.
If the diameter of ...
- 147
1
vote
0
answers
166
views
Build transportation system to travel between cities
Given $n$ cities, I'm looking to build a transportation system that allows travelling between every two cities.
For every two cities $i$ and $j$, a road can be paved in the cost of $c_{ij}$. Also, ...
- 215
1
vote
0
answers
71
views
Spanning tree with equally separated edge weights
I have a fully-connected graph $G=(V,E)$ with edge weights $w(v)\in\mathbb{R};v\in V$ and I need to find a spanning tree $T=(V_t\subseteq V,E_t\subseteq E)$ where the set of edge weights in the tree ...
- 141
1
vote
1
answer
178
views
Choosing spanning trees to maximise node connectivity
Given: n variables in X, and m sets of variables where each set, Ci contains a subset of X. I am trying to generate the graph G = (X, E) by picking the edges in E given the following constraints.
...
- 11
0
votes
0
answers
47
views
Recursively deleting spanning forest from graph, how many iterations maximum to get to the empty graph?
As in the question stated, I am interested in the approximation factor of the greedy approach to compute the arboricity of the graph.
My intuition tells me the factor should not be bigger than $2$, ...
- 294
0
votes
0
answers
235
views
Wrong Solution for `Spanning tree with chosen leaves` problem
Suppose that we're given a connected, undirected graph $G = (V, E)$ with
edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find
the lightest spanning tree in which the nodes of $U$ ...
- 1
0
votes
0
answers
19
views
Intuitively, my problem is a mix of perfect hashing, tree spanning, combinatorial stuff - Ordered Decision Tree?
The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem.
Imagine a row of commands:
...
0
votes
0
answers
195
views
Spanning-Tree-Protocol and BFS? (Distributed Computing)
Given is graph with networks and bridges/switches. We know, the root
Bridge is the bridge with the minimal Bridge-ID. The connections between every bridge and network is 1.
In the lecture slides they ...
- 219
0
votes
0
answers
209
views
Distributed MST in $O(n \log \log n)$
I'm facing the following problem:
Describe a distributed MST algorithm in time $O(n \log \log n)$
I've managed to think of the following,
Run GHS(Gallager, Humblet and Spira) algorithm, till there ...
0
votes
0
answers
329
views
How to efficiently find a minimum spanning tree?
I found this question from CSLR that I'm trying to figure out before my final.
You are given a weighted, connected, undirected graph G = (V, E) and
one of its minimum spanning trees T ⊆ E. Now ...
- 119
0
votes
0
answers
357
views
spanning tree of a DAG (directed acyclic graph) with less forward arcs
I am new to this algorithm and graphs. Just started learning. Could someone help me which algorithm is best suited to find the spanning tree of a Directed Acyclic Graph with less forward edges?
- 1
0
votes
0
answers
56
views
two connected graph - find linear spanning subgrap such that subgraph is still connected
Graph $G$ is 2-connected. It means that for each two edges there are exists at least to disjont (in terms of edges) paths.
Graph $G$ is not directed.
Our task is to find spanning subgraph $H$ of ...
- 553
0
votes
0
answers
84
views
Why if $G$ has two spanning trees $A$ and $A'$, then every edge of $A'\cup \{e_i\}\in A'$
Theorem:
Let be $G$ a weighted graph in which every edge has a different weight.
Suppose that $G$ has two spanning trees $A$ and $A'$.
Let be $i$ the first index such that $e_i\ne e'_i$ ...
-1
votes
1
answer
93
views
Prove following statement about Kruskal Algorithm
Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
