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

132 questions
Filter by
Sorted by
Tagged with
1answer
802 views

### Algorithm for finding all the heaviest edges in a graph

We have a non directed, not necessarily connected graph $G=(V,E)$, that is represented by a adjacency list, and a weight function $w:E \to R$. All edges have distinct weight. An edge is "heavy" if ...
1answer
619 views

### Improve minimum spanning tree with new edge, with better running time than O(|V|)?

The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \{u,v\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ ...
1answer
33 views

### Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights

I'm looking for an algorithm that gives a smallest value of 'travel cost' within the following constraints: a complete, connected, weighted graph, vertices are defined in 3d euclidean space, ...
1answer
47 views

### Distributed MST Construction in O(log log n) Rounds in a Clique

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5. It shows by induction on k (phase number), that ...
1answer
486 views

### How to understand the complexity of Kruskal implemented with Quick-Union by rank and path compression?

I'm trying to understand the complexity of the Kruskal algorithm implemented with the Quick-Union by rank and with the path compression. Now there is a theorem for the last structure above: The ...
1answer
160 views

### Expected Linear time Minimum Spanning Tree algorithm

I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST". My findings: I have read and search almost every available resource( main paper, wiki, reports on paper, lecture ...
1answer
294 views

### MST for a finite number of weights

Let $F$ be a finite set of real numbers say $\{w_1,\dots,w_k\}$. Let $G=(V,E)$ be an undirected connected graph and let $w\colon E\to F$ be a weight function. Describe a linear time algorithm that ...
1answer
523 views

### Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
1answer
4k views

### Remove Edge From Adjacency List

INPUT: weighted undirected graph in the form of adjacency list OUTPUT: adjacency list without the edge e Naive approach is: ...
1answer
1k views

### Bottleneck TSP with MST

There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far. ...
1answer
596 views

### Christofides algorithm: why must an MST have even number of odd-degree vertices?

This question is not necessarily related to Christofides algorithm per se, I just ran into it when reading about it. I assume that a minimum spanning tree must have an even number of odd-degree ...
1answer
202 views

### Must a min weight subset of edges connecting all vertices form a tree?

Got this question in an exam. In a graph where all edge weights are positive, if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree? True or ...
1answer
2k views

### Maximum Spanning Tree vs Maximum Product Spanning Tree

So I'm kind of wondering if I'm correct on something relating to an algorithms class. Let's say I want to, for whatever reason, find the maximum spanning tree of a graph such that the edge weight is ...
2answers
59 views

### Minimum spanning tree such that one edge can be minimised

During a computer coding exam, I have encountered such a problem. Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
1answer
43 views

### What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?

I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\_node$ is used to denote it previous node in the shortest path to the ...
1answer
74 views

### Define the time complexity of Kruskal's algorithm as function

I am trying to define the time complexity of Kruskal's algorithm as function dependant on: the number of vertices V the number of edges ...
1answer
50 views

2answers
478 views

### What is the point of the “respect” requirement in cut property of minimum spanning tree?

The cut property stated in terms of Theorem 23.1 in Section 23.1 of CLRS (2nd edition) is as follows. Theorem 23.1 Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight ...
2answers
212 views

### Equivalent definition of minimal spanning tree

Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$. It's my attempt to prove $\Rightarrow$: Consider the cycle ...
1answer
619 views

### How do deal with the following situations using Prim's algorithm?

Consider the following Graph We want to generate the MST using Prim's algorithm. Starting from node A, suppose we pick B as our next node, we see a self-loop that has less weight than the two other ...
1answer
1k 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....
0answers
10 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 ...
1answer
649 views

### DFS & BFS Spanning Trees

I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one. DFS: My understanding that to the ...
1answer
238 views

### MST Of An Almost Tree

A graph $G = (V,E)$ is called an almost tree if it is connected and has most $n + c$ edges where $n = |V|$ and $c$ is a small constant number. How would I go about designing an algorithm for a given ...
0answers
79 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, ...
0answers
69 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 ...
0answers
39 views

### Is a spanning tree an MST if its weight can't be decreased by adding an edge and removing one? [duplicate]

My gut says it's true and I have tested it on a few examples. However, I can't prove it. I thought of using contradiction; suppose there exists another tree T' with smaller weight which has m edges ...
0answers
31 views

### Graph of MSTs of a graph - 2 msts connected if differ by 1 edge - is this single-component? [duplicate]

Suppose we take all MSTs of a graph and build a new graph where each vertex corresponds to a MST of the first graph and two vertices are connected if their corresponding spannings trees differ by only ...
0answers
948 views

### All-pairs minimax path problem - MST [closed]

Let $G(V, E)$ be an undirected weighted (positive) graph. Given a path $s-t$ find the path that minimizes the maximum weight of any of its edges. This is the minimax path problem. It is know that a ...
0answers
237 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 ...
0answers
63 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 ...
0answers
336 views

### Working of the GHS algorithm

Can someone explain the working of the GHS algorithm using the graph given below. GHS is a distributed algorithm for finding the Minimum Spanning tree of a graph. The description of which can be found ...
2answers
2k views

### Is it possible for a maximum weight edge of a cycle being included in MST?

Let C be a cycle in a simple connected weighted undirected graph. Let "e" be an edge of maximum weight on C Which of the following is TRUE? (A) No minimum weight spanning tree contains e. (B) There ...
2answers
242 views

### Minimum Distance Spanning Tree Dijkstra

I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below: MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)} Is my ...
1answer
165 views

### Finding Euclidean Minimum Spanning Tree

Given a set of point $P$. Find the euclidean minimum spanning tree where each points is equally distributed on the plane using randomization. We can solve this problem with Prim's algorithm in \$O(n^2)...