# 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
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 ...
79 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 ...
409 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 ...
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, ...
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 ...
211 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$ (...
37 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?
35 views

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 ...
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 ...
50 views

I'm asking about the answer here: Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight? I didn't understand the best answer here Choose edge $e \in ... 1answer 133 views ### Boruvka MST algorithm using doubly linked lists I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following: Develop an implementation of Boruvka's algorithm that uses doubly-linked ... 1answer 96 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 ... 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 47 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 91 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 ... 1answer 117 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 57 views ### Distance function such that we visit every “color region” once [closed] Consider the following image: Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right. We must go through each color exactly once, and once we go outside a color, ... 1answer 59 views ### Combinatorial Optimization: Shortest distance given sets of drivers and riders Problem: I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to ... 1answer 35 views ### Minimum Spanning Tree with one particular edge minimised(continued) I have recently encountered a coding problem, specifically, the CCC problem S4. In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ... 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 58 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 137 views ### Optimal Loading of a Hopping Airplane Minimum Cost Flow Problem I have a Problem with an Optimal Loading a Hopping Airplane example . This is the Part of Minimum Cost Flow Problem.. .. I dont understand a Picture at all. I should to make one example with numbers ... 2answers 330 views ### Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says: At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable ... 3answers 107 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 ... 0answers 27 views ### Minimum spanning tree classification problem with adjacent neighbors I am new to minimum spanning trees. But have used the last few days on a problem I think matches MST, but cannot really figure out the connection. The problem is a minimum cost problem where N ... 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.... 2answers 52 views ### MST Proof (Kleinburg & Tordos) Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in ... 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 50 views ### Will MST find the shortest path for each pair$(r,v)$? Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes ... 1answer 84 views ### Minimum spanning subgraph of even degree I have an unusual problem that I am struggling to solve. I have a set of nodes (with positive distances between them) that I want to connect into a single component. In particular, I want to form a ... 1answer 73 views ### Generating a random minimum spanning tree I am tring to find the simplest method of generating a random minimum spanning tree. My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a ... 1answer 668 views ### Finding missing edge weights in the context of minimum spanning tree I came across following problem: Problem 1 Suppose that minimum spanning tree of the following edge weighted graph contains the edges with weights$x$and$z$, then what are$x$and$z$? The ... 1answer 162 views ### Two criteria for an edge to belong to all MSTs Let$G$be a connected undirected graph, with integral positive weights on the edges, and let$e_1$be an edge of$G$. As part of an assignment I proved the following Lemma 1: The edge$e_1$... 2answers 298 views ### Minimum spanning tree of a connected induced subgraph I'm doing an online course in which I'm struggling with the following multiple-choice question: Suppose$ T $is a minimum spanning tree of the connected graph$ G $. Let$ H $be a connected ... 1answer 150 views ### How to restore a broken minimal spanning tree? We're given$T$a minimal spanning tree (MST) of a non-directed, connected graph$G=(V,E)$with non-negative weights for each edge$e \in E$. Let$e^* \in T$be an edge in$T$and let$G'=(V,E')$be ... 1answer 648 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 45 views ### Proving that a spanning tree of graph is not a minimum Let$G$be an undirected and connected graph. Let$T$be a spanning tree of$G$with edges weights:$w_1 \le, w_2 \le ... \le w_{n-1}$which are responing to the edges.$e_1,e_2,...,e_{n-1}$. Now I ... 1answer 64 views ### Cost of the MST of the graph [closed] Studying for a test in a computer science class and cannot figure out the answer to this question. Any help would be appreciated! Although the picture shows a directed graph, please treat it as ... 1answer 31 views ### Why does the cut$(V_C,V-V_C)$respect$A$? Corollary 23.2 Let$G = (V,E)$be a connected, undirected graph with a real-valued weight function$w$defined on$E$. Let$A$be a subset of$E$that is included in some minimum spanning tree ... 2answers 773 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 ... 1answer 293 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 295 views ### NP-hardness of existence of spanning tree with given maximal degree I am trying to solve the following exercise: Let$G = (V,E)$be a graph. Show that the following two problems are NP-hard:$G$has a spanning tree where every node has at most$k$neighbors,... 3answers 126 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: ... 1answer 237 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 ... 1answer 39 views ### Proving equivalent definitions for MSTs I am working on the following homework exercise: Let$G = (V,E)$be an undirected graph and$c: E \rightarrow \mathbb{R}$it's cost function. Further let$T = (V,E')$be a spanning tree in G. I need ... 1answer 1k 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 ... 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)...
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: \$...