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.

38 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
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
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
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
408 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,...
user avatar
  • 141
2 votes
0 answers
54 views

Minimum unrooted binary spanning tree

Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices, and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints: tips have a degree of $1$ internal ...
user avatar
2 votes
0 answers
35 views

Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)

We have an algorithm problem in hand, can you please write your ideas about this, thank you! There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
user avatar
2 votes
0 answers
39 views

Does minimumm spanning tree always include the node with highest degree?

I want to know why the distances between nodes in a minimum spanning tree seems to be rooted to the node with highest degree. A bit of context here: I have spatial explicit weighted network that ...
user avatar
2 votes
0 answers
133 views

For which class of graphs can a minimum spanning tree always be associated to a shortest path tree?

Given a connected graph $G=(X,E)$ with positive edge weights. We assume that $G$ contains a unique min weight spanning tree $T_{\min}$ (this is true for example when for all the cuts, the edge with ...
user avatar
2 votes
0 answers
59 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 ...
user avatar
1 vote
0 answers
71 views

Is the minimum spanning tree a minimum-altitude connected subgraph

I'm not sure if my solution to the following problem (adapted from Exercise 20, Chapter 4 of Algorithm Design by Jon Kleinberg and Éva Tardos) is correct. I would appreciate it if anyone could point ...
user avatar
1 vote
0 answers
137 views

The Cut Lemma for graphs with non-distinct edges

In my introductory algorithms class I recently learned about the Cut Lemma and how it can be used to prove correctness for many Minimum Spanning Tree algorithms like Kruskal's and Prim's. In class, to ...
user avatar
1 vote
0 answers
89 views

Find minimum cycler in a graph

A graph G has n vertices and m edges The Minimum Cycler of G is a set S of edges of minimum total weight such that every cycle in G contains at least one edge in S. Devise an algorithm that finds the ...
user avatar
1 vote
1 answer
120 views

Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have ...
user avatar
  • 818
1 vote
0 answers
370 views

Kruskal naive implementation: how to use DFS to detect cycle in MST plus next edge?

Most discussion of naive (without Union-Find) implementations of Kruskal's algorithm for finding the minimal spanning tree that I see has a handwavy bit: "just use DFS to detect if there is a ...
user avatar
1 vote
1 answer
1k views

Updating a mst after increasing the weight of an edge in the mst

Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$ Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$. I'm using a common ...
user avatar
1 vote
1 answer
141 views

Minimum spanning tree formulation

Can any expert explain the reasoning behind the constraint in the following formulation of the minimum spanning tree? To formulate the minimum-cost spanning tree (MST) problem as an LP, we ...
user avatar
1 vote
0 answers
146 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, ...
user avatar
  • 215
1 vote
0 answers
122 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 ...
user avatar
  • 19
1 vote
0 answers
723 views

Using Prim's for finding minimum cost arborescence in a special setting

I have a complete graph G which is directed. In essence, a node is connected to all other nodes in the graph. Also, for every pair of nodes, say ...
user avatar
1 vote
0 answers
324 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 ...
user avatar
1 vote
0 answers
107 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 ...
user avatar
0 votes
0 answers
67 views

Wrong Solution for `Spanning tree with chosen leaves` problem

Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find the lightest spanning tree in which the nodes of $U$ ...
user avatar
  • 1
0 votes
0 answers
28 views

What are the real-world applications of the Minimum Bottleneck Spanning Tree?

I'm currently writing my Research Plan for a post-graduate application (MS level) in the field of Computational Geometry. So I'm looking into tackling the Euclidean Minimum Bottleneck Spanning Tree ...
user avatar
  • 123
0 votes
0 answers
26 views

Determining edges that occur in all minimum spanning trees

Given an undirected weighted connected graph. How to determine the edges that appear in all minimum spanning trees. I know the Kruskal and Prims algorithm to find a minimum spanning tree. But how does ...
user avatar
  • 19
0 votes
0 answers
29 views

Whats the benefit of using traverse to parent in union find?

I found most union find problem try to traverse through the parent for the find method But traversing seems unnecessary at times when using a set can achieve the ...
user avatar
0 votes
0 answers
41 views

Minimum spanning tree containing specific edges

Given a weighted undirected graph and a list of edges (without cycles), how can I create an MST that contains all those edges (or says that such an MST does not exist)?
user avatar
  • 1
0 votes
0 answers
34 views

Understanding the Rectilinear Spanning Tree Algorithm

I am required to find a Rectilinear Spanning Tree in $\mathcal{O(n\log(n))}$, where $n$ is the number of vertices to connect. A Rectilinear Spanning Tree is a spanning tree made of nodes where each ...
user avatar
0 votes
1 answer
41 views

Trace minimum spanning tree's path

I have a list of connected rooms, I need to visit each room in the list, but I have to record the exact path to traverse the entire graph. ...
user avatar
  • 21
0 votes
0 answers
40 views

Finding the smallest-cost way to deliver goods

I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each ...
user avatar
  • 1
0 votes
1 answer
120 views

Prove: If $T'$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

Prove: If $T'=(V,F')$ is a spanning tree, but not a MST of $G=(V,E)$, then there are edges $e' \in F'$ and $e \in $ $E$ \ $F'$ such that $w(e)<w(e')$ and $T'$ \ $\{e'\} \cup \{e\}$ is a spanning ...
user avatar
  • 133
0 votes
0 answers
50 views

Minimum spanning tree with given edges

So the question is: "Given an undirected graph G=(V,E) with positive edge weights, and E'⊆E, show an algorithm that finds, from all the minimum spanning trees, the one that has more edges from E' ".
user avatar
  • 11
0 votes
0 answers
43 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 ...
user avatar
0 votes
0 answers
191 views

How many roots are there in an undirected root

Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
user avatar
0 votes
0 answers
62 views

N-Guest Table, Graph Problem

The Queen of England wants to organize a set of tables for n guests talking different languages. The tables have to be set in a way that every guest can speak to his neighbor on the right and his ...
user avatar
0 votes
0 answers
169 views

Distributed MST in $O(n \log \log n)$

I'm facing the following problem: Describe a distributed MST algorithm in time $O(n \log \log n)$ I've managed to think of the following, Run GHS(Gallager, Humblet and Spira) algorithm, till there ...
user avatar
0 votes
0 answers
359 views

find all edges in a weighed tree that are heaviest edges in some cycle

Given an undirected graph $G=(V,E)$ and a weight function $w:E\to\{1,2,3,\dots,10\}$: Let $U\subseteq E$ the set of all edges $e\in E$ that has a cycle in $G$ such that the cycle contains $e$ and all ...
user avatar
-1 votes
1 answer
81 views

Prove following statement about Kruskal Algorithm

Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
user avatar