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
1
vote
1answer
1k 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 ...
1
vote
1answer
144 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 ...
1
vote
1answer
69 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 ...
1
vote
0answers
18 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 ...
1
vote
1answer
787 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 ...
1
vote
0answers
101 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, ...
1
vote
0answers
93 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 ...
1
vote
0answers
40 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 ...
1
vote
0answers
37 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 ...
1
vote
0answers
1k 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 ...
1
vote
0answers
281 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 ...
1
vote
0answers
80 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 ...
0
votes
2answers
3k 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 ...
0
votes
1answer
28 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
2answers
478 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 ...
0
votes
1answer
392 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)...
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 ...
0
votes
2answers
431 views

Spanning trees on disconnected graphs

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

Whether the 2 minimum spanning tree of same graph contains the lowest edges in common?

If two minimum spanning trees on the same graph only have 2 edges in common, then those two edges must be the lowest costs edges in the graph. True/false? and why? Because according to me if there ...
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
30 views

Is the subgraph of a mst an mst of the subgraph that its vertices represent

Let $G$ be a connected weighted undirected graph. Let $T$ be a mst of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T_a$ and $T_b$, where $Ta$ contains the vertex $a$...
0
votes
1answer
262 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 ...
0
votes
1answer
75 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, ...
0
votes
1answer
49 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 ...
0
votes
1answer
824 views

Time Complexity of the Kruskal Algorithm after sorting

In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?
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 ...
0
votes
1answer
170 views

What is the maximum possible degrees of a vertex of an MST

What is the number that a minimum spanning tree can have a vertex with degree at most? Is there any rule? Is it related to the number of vertex or edge? Or not?
0
votes
1answer
615 views

Turn MST of G to MST of G with one new edge

Given $T$, an MST of $G(V,E)$ connected and undirected. Assume we add an edge $e'$ with weight $w(e')$. Suggest an algorithm which takes $T$ as input, and outs $T'$ MST of $G'(V,E\cup\{e'\})$.So i ...
0
votes
4answers
1k 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 ...
0
votes
1answer
443 views

Is this “cycle” condition sufficient for unique minimum spanning tree?

Given a connected, undirected, weighted graph $G$, the condition The maximum-weight edge in any cycle of $G$ is unique. is not necessary for $G$ to have a unique minimum spanning tree (MST). ...
0
votes
1answer
713 views

Proof required for edges in a minimum spanning tree

G=(V,E) is an undirected simple graph in which each edge e has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are ...
0
votes
1answer
3k views

Kruskal's and Prim's algorithm [duplicate]

Does Kruskal's and Prim's algorithm work on directed graphs? I want the two algorithms to find a minimum spanning tree. For further enlightenment, I would like to know what other problems Kruskal's ...
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
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 ...
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
122 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 ...
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 ...
0
votes
2answers
923 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 ...
0
votes
0answers
39 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 ...
0
votes
2answers
78 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 ...
0
votes
1answer
90 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 ...
0
votes
0answers
129 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?
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 ...
0
votes
0answers
47 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 ...
0
votes
0answers
133 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 ...
0
votes
0answers
637 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 ...
0
votes
0answers
271 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 ...
0
votes
2answers
285 views

Question about time-complexity for MST-like algorithm

I have got a problem with an excercise about graphs: Your friend has been hired by a brewery to work out the most efficient delivery route for the beer-delivery truck drivers. A typical delivery has ...