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.

Filter by
Sorted by
Tagged with
28 votes
3 answers
39k 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 ...
user avatar
  • 467
14 votes
1 answer
6k 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 ...
user avatar
9 votes
3 answers
18k 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?
user avatar
8 votes
1 answer
2k 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?
user avatar
8 votes
2 answers
8k 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 ...
user avatar
  • 9,219
8 votes
1 answer
7k 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 ...
user avatar
  • 193
8 votes
0 answers
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 ...
user avatar
7 votes
1 answer
8k 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 ...
user avatar
6 votes
3 answers
2k views

Does the Minimum Spanning Tree include the TWO lowest cost edges?

Wikipedia's Minimum Spanning Tree reads: Minimum-cost edge If the minimum cost edge e of a graph is unique, then this edge is included in any MST. Proof: if e was not included in the MST, removing ...
user avatar
  • 291
6 votes
2 answers
173 views

Spanning tree in a graph of intersecting sets

Consider $n$ sets, $X_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words $$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\...
user avatar
  • 353
6 votes
2 answers
4k views

Counting Minimum Spanning Trees

I understand how Kruskal's algorithm works. However, I am not sure how to determine the number of minimum spanning trees that a given graph has. For example say graph $G=(V,E)$ given by When running ...
user avatar
  • 99
6 votes
2 answers
3k 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 ...
user avatar
  • 9,219
5 votes
2 answers
1k 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 ...
user avatar
  • 53
5 votes
2 answers
903 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 ...
user avatar
  • 115
5 votes
2 answers
613 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 ...
user avatar
5 votes
0 answers
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?
user avatar
4 votes
2 answers
1k 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 ...
user avatar
4 votes
2 answers
591 views

Spanning tree - minimum difference between smallest and largest weight

I am given an undirected, weighted graph $G$, on its base I have to create a spanning tree with such a property that the difference between the largest edge weight and the smallest edge weight is the ...
user avatar
  • 71
4 votes
2 answers
126 views

Can Edge Belong to a cycle if it is part of multiple BFS products

Given a simple connected undirected graph. with V vertices and E edges. Let e be some edge from E. If I perform |V| different BFS runs - meaning started each time from a different vertex - and in ...
user avatar
4 votes
1 answer
351 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 ...
user avatar
  • 141
4 votes
1 answer
1k 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 ...
user avatar
4 votes
1 answer
119 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 ...
user avatar
4 votes
2 answers
446 views

Edge exchange property of two Minimum Spanning Trees

Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T' Then I want to prove ...
user avatar
4 votes
2 answers
3k 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 ...
user avatar
4 votes
1 answer
191 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 ...
user avatar
  • 351
4 votes
1 answer
290 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 ...
user avatar
  • 327
4 votes
3 answers
1k 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$ (...
user avatar
  • 293
4 votes
1 answer
625 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 ...
user avatar
  • 41
3 votes
2 answers
443 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 ...
user avatar
3 votes
2 answers
5k 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....
user avatar
  • 139
3 votes
3 answers
452 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: An ...
user avatar
  • 163
3 votes
2 answers
225 views

Finding MST for connected graph with $|E|=|V|+87$

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 \...
user avatar
  • 51
3 votes
3 answers
944 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 ...
user avatar
  • 33
3 votes
2 answers
395 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: $...
user avatar
3 votes
1 answer
7k views

MST: Are all safe edges, light edges?

Following are some definitions from CLRS: DEFINITIONS : 1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides ...
user avatar
3 votes
1 answer
609 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 ...
user avatar
  • 4,371
3 votes
1 answer
1k 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 ...
user avatar
3 votes
1 answer
160 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 ...
user avatar
3 votes
1 answer
85 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 ...
user avatar
3 votes
1 answer
450 views

Is a subtree of a minimum spanning tree a minimum spanning tree of the subgraph spanned by the subtree?

Let $G$ be a connected weighted undirected graph. Let $T$ be a minimum spanning tree (MST) of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T_a$ and $T_b$, where $Ta$...
user avatar
3 votes
1 answer
111 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 ...
user avatar
3 votes
1 answer
346 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 ...
user avatar
3 votes
1 answer
646 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 ...
user avatar
  • 31
3 votes
1 answer
140 views

Find all edges of G contained in some MSP

I have the following question in a homework: Let $G = (V,E)$ be an undirected graph, and let $$A = \{ e \in E \mid \text{ s.t. exists an MSP $T$ containing } e\}.$$ We were asked to find $A$ in $O(m ...
user avatar
3 votes
1 answer
347 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 ...
user avatar
3 votes
0 answers
58 views

What is the name for this minimal satisfying set covering problem? [duplicate]

Preface Hello! I have a problem here that's difficult for me to Google, and I don't know if there's a name for it. It feels like a set cover problem of some kind, but I'm very unfamiliar with ...
user avatar
3 votes
0 answers
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 ...
user avatar
  • 23.9k
3 votes
1 answer
112 views

Proof that "local" minimum spanning tree is "global" minimum spanning tree

I'm trying to understand a proof from the book "Graph Theory with Application to Engineering & Computer Science" by Narsingh Deo. The chapter is about trees in non oriented graphs. A bit ...
user avatar
3 votes
0 answers
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) + ...
user avatar
  • 4,371
3 votes
0 answers
58 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$. ...
user avatar

1
2 3 4 5