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
6
votes
2answers
152 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\...
0
votes
0answers
13 views

Is there a way to solve the optimal branching / arborescence problem with path-dependent weights?

The optimal branching problem (solved by Edmond's algo or Tarjan's algo) finds the spanning arborescence for a particular graph. [0] I'm looking for a formulation of the problem that allows for path-...
0
votes
1answer
36 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 ...
1
vote
1answer
57 views

Finding an MST with one adding and removing vertex operation

I am facing the following problem: Given an undirected complete Euclidean weighted graph $G(V, E)$ and its MST $T$. I need to remove an arbitrary vertex $v_i \in V(G)$, and given a vertex $v_j \notin ...
1
vote
1answer
48 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$...
1
vote
1answer
70 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 ...
0
votes
1answer
29 views

Negative cycle detection using Bellman-Ford and its correctness

I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford. I have 2 doubts about the correctness of the algorithm: Why are we ...
0
votes
1answer
15 views

Minimum spanning tree with small set of possible edge weights

Given a undirected graph which only has two different edge weights $x$ and $y$ is it possible to make a faster algorithm than Prim's algorithm or Kruskal's algorithm? I saw on Kruskal's algorithm ...
0
votes
1answer
50 views

MST - algorithm to add an edge to the graph

I have some difficulty proving the correctness of my solution to the following exercise. Let $G = (V,E)$ undirected connected graph, $w \colon E \to \mathbb{R}$ weight function. Let $T$ a MST (minimum ...
0
votes
3answers
2k views

Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged

Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of $e$ decreases by some positive number, how to prove the the MST is unchanged (still $T$) ? It seems obvious by ...
1
vote
1answer
198 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 ...
0
votes
2answers
42 views

Will the minimum spanning tree not have only those edges specified by the cycle property? [duplicate]

I have just started to understand the "Minimum Spanning Trees" (MSTs), and had come across the cycle property. I am referring to the book - Algorithm Design by Jon Kleinberg and Eva Tardos. The ...
3
votes
1answer
3k 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....
2
votes
3answers
152 views

MST with degree constraints on some node

While preparing for an algorithms exam I came across the following problem in a practice test: Let $G = (V,E)$ be a connected, undirected graph with weighted edges (all weights are rational numbers ...
0
votes
0answers
36 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' ".
0
votes
1answer
24 views

spanning tree implemented by a min priority queue [closed]

if it is executed on unconnected graphs what will it execute? I thought it won't execute since it is unconnected but since it is being implemented by min priority queue, will that affect the results?
0
votes
1answer
178 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 ...
1
vote
2answers
149 views

Minimum-average-cost subtree that is not necessarily spanning

I'm looking for an efficient algorithm for the following problem: Input: a rooted tree (undirected) with a cost on each edge. It could be considered directed away from the root (or towards the root)....
2
votes
1answer
1k views

Can the heaviest edge ever be in an MST?

Is it true that the heaviest edge in a directed graph can not be in the MST of that graph? I don't think it is true because we might end up with a heaviest edge that is not part of a cycle. Can ...
2
votes
0answers
95 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 ...
8
votes
0answers
98 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 ...
2
votes
1answer
459 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 ...
1
vote
2answers
293 views

Graph with exactly 2 Minimum Spanning Trees

Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs). Given this condition stipulated, prove that any cycle formed by all the edges in both the MSTs (i.e., the union of the edges in ...
3
votes
1answer
57 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 ...
3
votes
2answers
1k 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 ...
8
votes
2answers
6k 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 ...
4
votes
3answers
602 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$ (...
0
votes
1answer
132 views

If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST? [duplicate]

Let's say that I have an MST, $T$. I pick an edge not in $T$ and change its weight, and add it to $T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST? MST means ...
3
votes
1answer
61 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 ...
0
votes
0answers
96 views

Boruvka algorithm in Elog(log(V)) complexity

I am trying to implement Boruvka algorithm with the use of fibonacci heaps. My idea is the following: Since Boruvka's algorithm operates like this: Input is a connected, weighted and un-directed ...
2
votes
1answer
34 views

Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]

I'm pracitcing exams towards finals, Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$. Prove : for every 2 ...
0
votes
1answer
267 views

adding an edge, Is T still a MST to the new graph?

Suppose I have a minimum spanning tree $T$ in a graph $G=(V,E)$ with positive edge weights $w$. Provide an algorithm that after adding a new edge $e$ with a unique weight $w(e)$ to $G$, returns true ...
-1
votes
1answer
96 views

Is there an example of when DFS will not return the min. spanning tree?

If we have a connected, weighted, undirected graph. Can anyone provide an example where DFS will not return the MST? No matter what vertex we start from ?
1
vote
1answer
59 views

Special case of the $MST-$ Problem

I am working on the following exercise: Consider an undirected complete graph $G(V,E)$ and positive real numbers $a_1,a_2,\ldots,a_n$. The task is to find a MST with respect to the edge weights $...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
-1
votes
2answers
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....
0
votes
4answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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, ...
1
vote
1answer
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 ...
2
votes
2answers
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?
0
votes
2answers
453 views

Spanning trees on disconnected graphs

Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?
2
votes
1answer
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 ...
0
votes
2answers
488 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 ...
1
vote
1answer
111 views

Do the minimum spanning trees of a graph have the same number of edges with a given weight?

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 ...
3
votes
1answer
315 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 ...