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

160 questions
Filter by
Sorted by
Tagged with
152 views

33 views

### Sensitivity analysis of $MST$ edges

I am working on the following exercise: Consider an undirected graph $G = (V,E)$. Let $T^* = (V,E_{T^*})$ be a $MST$ and let $e$ be an edge in $E_{T^*}$. We define the set of all values that can be ...
2k views

### Time complexity of kruskal using array data structure

I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps: Sort the edges as ...
2k views

### Prim's algorithm - misunderstanding

I have to demonstrate Prim's algorithm for an assignment and I'm surprised that I found two different solutions, with different MSTs as an outcome. Now I now that shouldn't happen, so I wonder what I ...
5k views

### Minimum spanning tree using DFS and BFS

Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs? I have gone through many answers but each answer says something different and I am not convinced....
2k views

### Questions on shortest path and minimum spanning tree

T/F Questions Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Solution - False I think this should be True, as Dijkstra's Algorithm ...
19 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 ...
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 ...
532 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 ...
68 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, ...
849 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 ...
118 views

### Uniqueness of minimum spanning tree

If G has a unique minimum spanning tree, does that mean the edge weights in G are also unique? if yes why and if no why?
453 views

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