# 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.

155 questions
Filter by
Sorted by
Tagged with
22k views

### When is the minimum spanning tree for a graph not unique

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G? I know that the MST is unique when all of the weights are distinct, but ...
3k views

### Are all MST minimum spanning trees reachable by Kruskal and Prim?

I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for ...
11k views

### Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?
1k views

### Does a graph always have a minimum spanning tree that is binary?

I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?
6k views

### Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$. Now we decrease the weight by $k$ of ...
89 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 ...
5k views

### Finding MST after adding a new vertex

Let $G=(V,E)$ which is undirected and simple. We also have $T$, an MST of $G$. We add a vertex $v$ to the graph and connect it with weighted edges to some of the vertices. Find a new MST for the new ...
651 views

### MST with half the edges the maximum weight

I have been cracking my head over the following question - You are given an undirected connected graph with an even number of edges. Half of the edges have weight less than C (possibly with ...
683 views

### Is the inverse of MST cycle property always true? Why?

I am trying to find an algorithm which would check for each edge in a given weighted undirected graph whether it belongs to any of the graph's Minimum Spanning Trees. I have found many potential ...
2k views

### Find all critical edges for minimum spanning tree

This is a problem from the textbook "Algorithms, 4th edition" by Robert Sedgewick and Kevin Wayne. 4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to ...
99 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?
707 views

### Diameter-constrained Minimum Spanning Tree Problem

The diameter-constrained Minimum Spanning Tree (MST) problem is as follows: you have a undirected weighted graph $G = (V,E)$ of different weights where $V$ is the set of vertices and $E$ is the set of ...
6k views

### Why do we have different algorithm for MST when graphs are directed?

What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ? What cases are not ...
308 views

### Are all minimum spanning trees optimized for fairness?

I know by definition that a minimum spanning tree (MST) of a weighted, connected graph has the lowest global value for for sum of all edges in a path that connects all vertices. I'm curious if all ...
82 views

### Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1)

There is a finite set of points $S$ in the plane with $|S| = n$. MST is the minimal spanning tree of S. "Minimal" here refers to the Euclidean distance between the points of $S$, so the MST is the ...
140 views

### Is a perfect matching's weight less than MST of a metric graph?

This is part of a bigger proof I'm trying to solve, which eventually came down to one thing: Let $G=(V,E)$ an un-directed, complete, metric graph (maintains the triangle inequality) with an even ...
163 views

### Between every two MST's there's a series of “nearby” MST's

Given undirected connected graph $G=(V,E)$ and a weight function $w:E\to\mathbb{R}$, two MST's $T_1, T_2$ are nearby if there exists $e\in T, e'\in T'$ such that $T'=(T-\{e\})\cup\{e'\}$. Prove that ...
581 views

### Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?

Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$. Now let $T'$ be some other spanning tree of $G$ (...
402 views

### Alternative algorithm for minimum spanning tree construction

Let $\textit{G(V,E)}$ be an undirected connected graph with distinct costs on its edges. Initialize $\textit{T}$ to be any spanning tree of $\textit{G}$. Consider an algorithm which replaces an ...
475 views

### Minimum spanning tree formulation as integer program

The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a ...
478 views

### Minimum diameter spanning tree problem

Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $G(V, E)$, weight function $w: E \rightarrow R, w(e) > 0\ \forall e \in E$, find the ...
424 views

### Minimum path - robot motion problem combined with freeze tag problem

Alright, I am not entirely sure if this is the right place to ask this, but here goes: I have a map of coordinates of robots and obstacles. The first robot is awake from the start of the problem and ...
183 views

Given $G=(V,E)$ undirected, connected graph and weights given by $w:E \to \mathbb R$. We also know that $|E|=|V|+87$. Find Minimum spanning tree of $G$. Obviously we can use Prim in $O(|V| \cdot \... 3answers 228 views ### MST: Is there such an example of a graph with unique mst and not unique light edge? The problem is the following: Give an example of a graph that has a unique minimum spanning tree but for every cut of the graph, there is not a unique light edge crossing the cut. I am trying to ... 2answers 2k views ### Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree? I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST). From my understanding: The ... 1answer 2k views ### What edges are not in any MST? This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed. Consider a weighted undirected graph.... 1answer 309 views ### Maximal Minimum Spanning Tree by Removing$k$Edges The problem is as follows: Consider a connected, undirected, and weighted graph$G = (V, E, w)$and an integer$0 < k < |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove ... 1answer 415 views ### What is the formal way to prove this is still a minimum spanning tree? I don't get the formal way of proving the following cases: Suppose I have a minimum spanning tree$T$in a graph$G(V, E)$, with positive edge weights$w$, I want to prove the following: 1) If I ... 1answer 118 views ### Algebraic (spectral) algorithms for the minimum spanning tree problem Are there any algorithms that use the spectral properties of a graph to solve the minimum spanning tree problem? To clarify further what I have in mind, starting with the Laplacian matrix I want to ... 1answer 83 views ### Finding minimum spanning tree of a special form graph I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form: My idea was a recursive solution: Suppose the algorithm ... 1answer 55 views ### how to generate all spanning trees from one spanning tree If I have one spanning tree from a connected and undirected graph, how can I generate all other spanning trees of this graph by modifying this spanning tree one edge at a time? All intermediates must ... 1answer 205 views ### Constructing a minimum spanning tree from an all-shortest path graph? Given an$n \times n$shortest path distance matrix$D$. And a complete graph$G(D)$on$n$nodes, where edge$(i, j)$has weight$D_{ij}$. Furthermore, the distance matrix$D$is computed for a ... 1answer 206 views ### What is the best way to merge cycles to minimise total weight? Suppose I have a vertex-disjoint set$S$of simple cycles in a weighted undirected graph. So no vertex$v$is contained in more than one cycle. A cycle$c$is a closed path with no repeated vertices:$...
Suppose for a graph $G=(V,E)$ and a spanning tree T of G, $\Delta(T)$ is the largest degree of a vertex in T, and let $\Delta^*$ be the smallest such quantity over all spanning trees of $G$. We have ...