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

130 questions
3answers
14k 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 ...
1answer
1k 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 ...
3answers
6k 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?
1answer
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?
2answers
4k 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 ...
1answer
3k 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 ...
2answers
448 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 ...
2answers
532 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 ...
2answers
648 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 ...
0answers
79 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?
2answers
539 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 ...
1answer
257 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 ...
1answer
66 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 ...
1answer
4k 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 ...
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
91 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 ...
1answer
414 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 ...
3answers
163 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$ (...
0answers
380 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,...
1answer
69 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 ...
2answers
401 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 ...
2answers
148 views

1answer
66 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
280 views

### If all edges are unweighted AND DIRECTED, can one use BFS to obtain a MST?

I've looked through CS SE and I've found a page that said you could find use BFS to find a MST if the edges are unweighted, but what if the edges are directed? Given a directed graph between V ...
1answer
67 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
48 views

### Algorithm for MST connecting a subgraph

I already know how to find the MST of a connected graph. This MST will have the least total weight and will connect all nodes in the graph. However, this is a problem I have to deal with: Given a ...
1answer
247 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 ...
1answer
122 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 ...
1answer
362 views

### Local search to find minimum degree spanning tree

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 ...
0answers
44 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) + ...
0answers
41 views

### Edge that is not a light edge in a MST [duplicate]

Given the following statement: For a graph $G$, consider its minimum spanning tree $T$ and let $e = (a,b)$ be an edge that is not a light edge for a given cut $C$. Then $e$ never belongs to $T$. ...
1answer
816 views

### Shortest paths in weighted graphs, and minimum spanning trees

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
3answers
105 views

### Need Help Understanding MST Cutset Formulation

I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation). This is the definition: ...
2answers
446 views

### Does MST exclude the edge belongs to the cycle of the graph?

For any simple, connected, undirected graph $G(V,E,w)$ with each carrying distinct positive edge weights, is it true that MST will contain all the edges which do not lie in any cycle of $G$? I think ...
1answer
109 views

### Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?

I am trying to prove the algorithm for Question 5 in this practice exam. I am trying to prove this algorithm with the following three claims: Suppose we have a graph G, a minimum spanning tree T, ...
1answer
2k views

### safe edge for Minimum spanning tree

I know this question is posted many times, but i am still posting this because i have my own doubt which pulls me out to move forward to kruskal and prim's algorithm.So Please do help me out $-:$ ...
2answers
329 views

### MSTs in Christofides Algorithm

I am implementing the Christofides algorithm for TSP problem and currently I have one issue with the MST result. Let's assume that I have one graph $G$, whereas I can get $MST_1$ and $MST_2$ where ...
1answer
281 views

### Understanding the Diameter Constrained MST Problem

I am interested in understanding the DCMST problem, explained in this paper (http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf). I don't think I understand it as I should. Here is how I understand ...
1answer
339 views