You are given an undirected graph G with weighted edges and a minimum spanning tree T of G.

Question

Question

You are given an undirected graph G with weighted edges and a minimum spanning tree T of G.

You are given an undirected graph G with weighted edges and a minimum spanning tree T of G. Design an algorithm to update the minimum spanning tree when the weight of a single edge is decreased.

The input to your algorithm should be the edge e and its new weight; your algorithm should modify T so that it is still a MST. Analyze the running time of your algorithm and prove its correctness.

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

Algorithm:

1. Check whether edge whose weight is decreased exists in T

2. If it exists then MST will not change but weight of MST will be decreased

3. If edge is not present in MST then add that edge to MST

4. A cycle is formed in MST. Delete the heaviest edge from cycle to get new MST.

Complexity: O(V) as a cycle of maximum V vertices need to be traversed.

Precondition: MST given

Postcondition: MST from algorithm

The algorithm will always return a MST if T is MST.

Add a comment

Answer 2

Similar Homework Help Questions

You are given an undirected graph G with weighted edges and a minimum spanning tree T of G.

You are given an undirected graph G with weighted edges and a minimum spanning tree T of G. Design an algorithm to update the minimum spanning tree when the weight of a single edge is increased. The input to your algorithm should be the edge e and its new weight: your algorithm should modify T so that it is still a MST. Analyze the running time of your algorithm and prove its correctness.
Consider the following weighted undirected graph.

Consider the following weighted undirected graph. (a) Explain why edge (B, D) is safe. In other words, give a cut where the edge is the cheapest edge crossing the cut. (b) We would like to run the Kruskal's algorithm on this graph. List the edges appearing in the Minimum Spanning Tree (MST) in the order they are added to the MST. For simplicity, you can refer to each edge as its weight. (c) 1We would like to run the Prim's algorithm on this...
IN JAVA Given is a weighted undirected graph G = (V, E) with positive weights and...

IN JAVA Given is a weighted undirected graph G = (V, E) with positive weights and a subset of its edges F E. ⊆ E. An F-containing spanning tree of G is a spanning tree that contains all edges from F (there might be other edges as well). Give an algorithm that finds the cost of the minimum-cost F-containing spanning tree of G and runs in time O(m log n) or O(n2). Input: The first line of the text file...

Given the following weighted graph G. use Prim's algorithm to determine the Minimum-Cost Spanning Tree (MCST)...

Given the following weighted graph G. use Prim's algorithm to determine the Minimum-Cost Spanning Tree (MCST) with node 1 as the "root". List the vertices in the order in which the algorithm adds them to the solution, along with the edge and its weight used to make the selection, one per line. Each line should look like this: add vertex y: edge = (x,y), weight = 5 When the algorithm ends there are, generally, edges left in the heap. List...
Problem 3's picture are given below. 5. (a) Let G = (V, E) be a weighted connected undirected simple graph. For n...

Problem 3's picture are given below. 5. (a) Let G = (V, E) be a weighted connected undirected simple graph. For n 1, let cycles in G. Modify {e1, e2,.. . ,en} be a subset of edges (from E) that includes no Kruskal's algorithm in order to obtain a spanning tree of G that is minimal among all the spanning trees of G that include the edges e1, e2, . . . , Cn. (b) Apply your algorithm in (a)...
Let G = (V, E) be a weighted undirected connected graph that contains a cycle. Let...

Let G = (V, E) be a weighted undirected connected graph that contains a cycle. Let k ∈ E be the edge with maximum weight among all edges in the cycle. Prove that G has a minimum spanning tree NOT including k.

Problem 5. (15 marks) Given a connected, undirected, weighted graph G- (V, E), define the cost...

Problem 5. (15 marks) Given a connected, undirected, weighted graph G- (V, E), define the cost of a spanning tree to be the maximum weight among the weights associated with the edges of the spanning tree. Design an efficient algorithm to find the spanning tree of G which maximize above defined cost What is the complexity of your algorithm.
Let G=(V, E) be a connected graph with a weight w(e) associated with each edge e....

Let G=(V, E) be a connected graph with a weight w(e) associated with each edge e. Suppose G has n vertices and m edges. Let E’ be a given subset of the edges of E such that the edges of E’ do not form a cycle. (E’ is given as part of input.) Design an O(mlogn) time algorithm for finding a minimum spanning tree of G induced by E’. Prove that your algorithm indeed runs in O(mlogn) time. A minimum...
2. Let G = (V, E) be an undirected connected graph with n vertices and with...

2. Let G = (V, E) be an undirected connected graph with n vertices and with an edge-weight function w : E → Z. An edge (u, v) ∈ E is sparkling if it is contained in some minimum spanning tree (MST) of G. The computational problem is to return the set of all sparkling edges in E. Describe an efficient algorithm for this computational problem. You do not need to use pseudocode. What is the asymptotic time complexity of...

MST For an undirected graph G = (V, E) with weights w(e) > 0 for each edge e ∈ E, you are given a MST T. Unfortunately one of the edges e* = (u, z) which is in the MST T is deleted from the graph G...

MST For an undirected graph G = (V, E) with weights w(e) > 0 for each edge e ∈ E, you are given a MST T. Unfortunately one of the edges e* = (u, z) which is in the MST T is deleted from the graph G (no other edges change). Give an algorithm to build a MST for the new graph. Your algorithm should start from T. Note: G is connected, and G − e* is also connected. Explain...

You are given an undirected graph G with weighted edges and a minimum spanning tree T of G.

Homework Answers

Add Answer to:
You are given an undirected graph G with weighted edges and a minimum spanning tree T of G.

Post as a guest

Earn Coins