# Questions tagged [minimum-spanning-tree]

Use this tag whenever your question is related to minimum spanning tree (MST). An MST of a connected edge-weighted graph G is a spanning tree whose sum of edge weights is as small as possible. We usually assume $G$ is finite, simple and undirected.

38 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
161 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 ...
114 views

### Minimum spanning tree and Hamiltonian path

For a graph $G(V,E)$, under what conditions is a minimum spanning tree of $G$ equal to a hamiltonian path on $G$? IS there any body of literature connecting these two?
74 views

### A simple algorithm to solve the MST Sensitivity Analysis problem in linear time when the MST is a path

The problem. Given an undirected, connected, edge-weighted graph $G=(V, E_G; w)$ and a minimum spanning tree (MST) $T=(V, E_T)$ of $G$, the MST sensitivity analysis problem asks to find, for each ...
• 23.9k
52 views

### Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

I have a graph algorithm that runs in:  T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + ...
• 4,371
408 views

### Learning automata for degree constrained minimum spanning tree problem

I'm trying to understand the algorithm described in "Degree constrained minimum spanning tree problem: a learning automata approach" (Javad Akbari Torkestani, The Journal of Supercomputing; April 2013,...
• 141
54 views

### Minimum unrooted binary spanning tree

Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices, and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints: tips have a degree of $1$ internal ...
• 121
35 views

### Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)

We have an algorithm problem in hand, can you please write your ideas about this, thank you! There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
• 21
39 views

### Does minimumm spanning tree always include the node with highest degree?

I want to know why the distances between nodes in a minimum spanning tree seems to be rooted to the node with highest degree. A bit of context here: I have spatial explicit weighted network that ...
133 views

### For which class of graphs can a minimum spanning tree always be associated to a shortest path tree?

Given a connected graph $G=(X,E)$ with positive edge weights. We assume that $G$ contains a unique min weight spanning tree $T_{\min}$ (this is true for example when for all the cuts, the edge with ...
59 views

### Minimum Weight Binary Spanning Tree

Let $G=(V,E)$ be a simple graph with weights $w_{ij}$ (can be assumed to be positive). Is it possible to find the minimum (or maximum) weight, rooted spanning tree that is binary? That means every ...
1 vote
71 views

### Is the minimum spanning tree a minimum-altitude connected subgraph

I'm not sure if my solution to the following problem (adapted from Exercise 20, Chapter 4 of Algorithm Design by Jon Kleinberg and Éva Tardos) is correct. I would appreciate it if anyone could point ...
1 vote
137 views

### The Cut Lemma for graphs with non-distinct edges

In my introductory algorithms class I recently learned about the Cut Lemma and how it can be used to prove correctness for many Minimum Spanning Tree algorithms like Kruskal's and Prim's. In class, to ...
1 vote
89 views

### Find minimum cycler in a graph

A graph G has n vertices and m edges The Minimum Cycler of G is a set S of edges of minimum total weight such that every cycle in G contains at least one edge in S. Devise an algorithm that finds the ...
• 145
1 vote
120 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
370 views

### Kruskal naive implementation: how to use DFS to detect cycle in MST plus next edge?

Most discussion of naive (without Union-Find) implementations of Kruskal's algorithm for finding the minimal spanning tree that I see has a handwavy bit: "just use DFS to detect if there is a ...
• 111
1 vote
1k views

### Updating a mst after increasing the weight of an edge in the mst

Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$ Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$. I'm using a common ...
• 11
1 vote
141 views

### Minimum spanning tree formulation

Can any expert explain the reasoning behind the constraint in the following formulation of the minimum spanning tree? To formulate the minimum-cost spanning tree (MST) problem as an LP, we ...
1 vote
146 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
122 views

### n'th cheapest MST in a graph, with multiple edges that can have the same weight

I'm trying to think about an algorithm for this problem. I know there is an algorithm for the second cheapest MST in a graph, but if I understood it correctly it only solves cases in which every ...
• 19
1 vote
723 views

### Using Prim's for finding minimum cost arborescence in a special setting

I have a complete graph G which is directed. In essence, a node is connected to all other nodes in the graph. Also, for every pair of nodes, say ...
1 vote
324 views

### How can I modify Kruskal's algorithm to work with limited resources?

In Kruskal algorithm, I decided to use it to construct a minimum spanning tree for a set of N = 100,000 points. Since my hardware does not allow me to keep all the distances between pairs of points, I ...
1 vote
107 views

### NP-hardness of Capacitated Minimum Spanning Tree and Price Collecting Steiner Tree on dag/tree

I am thinking about the NP-completeness of two graph problems on different graph structures. For example: The Capacitated Minimum Spanning Tree for graph is NP-hard. However, is the problem still ...
• 335
67 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$ ...
28 views

### What are the real-world applications of the Minimum Bottleneck Spanning Tree?

I'm currently writing my Research Plan for a post-graduate application (MS level) in the field of Computational Geometry. So I'm looking into tackling the Euclidean Minimum Bottleneck Spanning Tree ...
• 123
26 views

### Determining edges that occur in all minimum spanning trees

Given an undirected weighted connected graph. How to determine the edges that appear in all minimum spanning trees. I know the Kruskal and Prims algorithm to find a minimum spanning tree. But how does ...
• 19
29 views

### Whats the benefit of using traverse to parent in union find?

I found most union find problem try to traverse through the parent for the find method But traversing seems unnecessary at times when using a set can achieve the ...
• 101
41 views

### Minimum spanning tree containing specific edges

Given a weighted undirected graph and a list of edges (without cycles), how can I create an MST that contains all those edges (or says that such an MST does not exist)?
• 1
34 views

### Understanding the Rectilinear Spanning Tree Algorithm

I am required to find a Rectilinear Spanning Tree in $\mathcal{O(n\log(n))}$, where $n$ is the number of vertices to connect. A Rectilinear Spanning Tree is a spanning tree made of nodes where each ...
41 views

### Trace minimum spanning tree's path

I have a list of connected rooms, I need to visit each room in the list, but I have to record the exact path to traverse the entire graph. ...
• 21
40 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 ...
• 1
120 views

### Prove: If $T'$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

Prove: If $T'=(V,F')$ is a spanning tree, but not a MST of $G=(V,E)$, then there are edges $e' \in F'$ and $e \in$ $E$ \ $F'$ such that $w(e)<w(e')$ and $T'$ \ $\{e'\} \cup \{e\}$ is a spanning ...
• 133
50 views

### Minimum spanning tree with given edges

So the question is: "Given an undirected graph G=(V,E) with positive edge weights, and E'⊆E, show an algorithm that finds, from all the minimum spanning trees, the one that has more edges from E' ".
• 11
43 views

### Minimum spanning tree classification problem with adjacent neighbors

I am new to minimum spanning trees. But have used the last few days on a problem I think matches MST, but cannot really figure out the connection. The problem is a minimum cost problem where N ...
191 views

### How many roots are there in an undirected root

Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
62 views

### N-Guest Table, Graph Problem

The Queen of England wants to organize a set of tables for n guests talking different languages. The tables have to be set in a way that every guest can speak to his neighbor on the right and his ...
169 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 ...
359 views

### find all edges in a weighed tree that are heaviest edges in some cycle

Given an undirected graph $G=(V,E)$ and a weight function $w:E\to\{1,2,3,\dots,10\}$: Let $U\subseteq E$ the set of all edges $e\in E$ that has a cycle in $G$ such that the cycle contains $e$ and all ...
• 712
81 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 ...