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.

25 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8 votes
0 answers
198 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 ...
I_Really_Want_To_Heal_Myself's user avatar
6 votes
0 answers
776 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-...
ilija's user avatar
  • 61
5 votes
0 answers
169 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$...
Jordan B Meir's user avatar
4 votes
1 answer
148 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. ...
Bassem's user avatar
  • 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.'s user avatar
  • 159k
2 votes
0 answers
62 views

Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...
Nathaniel's user avatar
  • 15.6k
2 votes
0 answers
40 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 ...
Ash Ketchum's user avatar
2 votes
0 answers
63 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 ...
Ash Ketchum's user avatar
2 votes
0 answers
73 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 ...
abhi01nat's user avatar
  • 141
1 vote
0 answers
224 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 ...
Redwanul Sourav's user avatar
1 vote
0 answers
190 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, ...
Itay4's user avatar
  • 215
1 vote
0 answers
75 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 ...
thayne's user avatar
  • 141
1 vote
1 answer
190 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. ...
fli's user avatar
  • 11
0 votes
0 answers
14 views

Prove that the a bottleneck of path P is maximal

As the title says, the question is about finding the maximal bottleneck edge in path P. Bottleneck of a path P in an undirected graph G = (V,E) is defined to be the weight of the edge with minimal ...
Salty Champ's user avatar
0 votes
2 answers
103 views

Distinct edge weights assumption in second best MST algorithms only replacing an edge in MST

In a CP-algorithms wiki Second Best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor: Let  $T$  be the Minimum Spanning Tree of a graph $G$ . It can be observed, that the second best ...
Kenneth Kho's user avatar
0 votes
0 answers
43 views

Find spanning tree by removing heaviest weight

I need to design the following algorithm: Given an undirected, simple, and connected graph $G=(V,E)$ and some positive weight function $w$. The algorithm needs to scan the edges from the heavier edge ...
Joe's user avatar
  • 1
0 votes
0 answers
341 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$ ...
Robert's user avatar
  • 1
0 votes
0 answers
21 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: ...
Anony Pony's user avatar
0 votes
0 answers
207 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 ...
M.Mac's user avatar
  • 219
0 votes
0 answers
237 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 ...
Jeremy Shiklov's user avatar
0 votes
0 answers
343 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 ...
Andrew Raleigh's user avatar
0 votes
0 answers
386 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?
sakshi's user avatar
  • 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 ...
user40545's user avatar
  • 573
0 votes
0 answers
85 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$ ...
Revolucion for Monica's user avatar
-1 votes
1 answer
95 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 ...
Kate Austen's user avatar