Question: For an undirected, connected graph G = (V, E) with weights w(e) > 0, you are given a MST, T. Unfortunately one of the edges

For an undirected, connected graph G = (V, E) with weights w(e) > 0, you are given a MST, T. Unfortunately one of the edges e=(u, v) 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. Note: G is connected, and G e is also connected. Your algorithm should be correct and faster in O() than building a MST from scratch (so using Prims or Kruskals will receive little credit).

***

You are allowed to use the algorithms from class as black-boxes. Black-box graph algorithms should be used without modification.

* DFS (outputs connected components, a path between two vertices, topological sort on a DAG. You also have access to the pre and post arrays!), BFS and the Explore subroutine.

* Dijkstras algorithm to find the shortest distance from a source vertex to all other vertices and a path can be recovered backtracking over the pre labels.

* Bellman-Ford and Floyd-Warshall to compute the shortest path when weights are allowed to be negative.

* SCCs which outputs the strongly connected components, and the metagraph of connected components.

* Kruskals and Prims algorithms to find MST.

* Ford-Fulkerson and Edmonds-Karp to find max flow on networks.

When using a black-box, make sure you clearly describe which input you are passing to it and how you use the output from or take advantage of the data structures created by the algorithm. Your solution must:

- Include the description of your algorithm in words (no pseudocode!).

- Explain the correctness of your design.

- State and analyze the running time of your design.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

can you answer these questions Consider an undirected connected graph G : (V, E) with edge costs (36 > 0 for e E E which are all distinct. (a) Let E' C; E be dened as the following set of edges: for...

Other answer is incorrect Problem 1. (15 points) Consider an undirected connected graph G = (V, E) with edge costs ce > 0 for e E which are all distinct. (a) [8 points). Let E' CE be defined as the...

Consider the minimum spanning tree (MST) problem. Namely, lets say given a connected graph G - (V, E) with weights w ER, find a spanning tree T E minimizing ETw(e). The generalization to a weighted...

Computer Systems Modelling Consider a birth death model with birth rates n in states n = 0, 1, . . . and death rates n in states n = 1, 2, . . .. (a) State the detailed balance conditions for the...

where the degree of a node in one partition is the number of edges incident to the node in that partition. Show that the solution obtained (S1,S2) by algorithm Local Search MAX-CUT is at least 1/2 of...

Problem 3 . Suppose we are given a undirected weighted graph G = ( V , E; w ) , where w : E - > R is the map to assign a weight w ( e ) to each edgee in E . Let T be a minimum spanning tree of G . a...

Let's consider linear programming formulations of the minimum spanning tree problem. We now have an (undirected) graph G = (V, E) and weights w : E R+. As we discussed in class, one way of phrasing...

Given an undirected connected graph G = (V, E) with |V | = n nodes, let u and v be two nodes in G such that their distance is greater than n/2, i.e., the shortest path between u and v has at least n...

A poll on a website asked respondents what they thought was the best method of losing weight. 65% picked exercise as the answer. If five randomly selected visitors to the website were asked this...

At what point on "The Clock" was Travis Scott before his recent concert in Houston Texas? a. 9:00 b. 6:00 c. 12:00 d. 3:00

When an accounts receivable clerk is allowed to steal one customers payment and apply the next one toward that payment and so on , this is a violation of: Group of answer choices segregation of...

Compared with half a century ago, adoption has become _ _ _ _ _ _ _ _ _ common, but it is more open and acceptabl e , so we probably discuss it _ _ _ _ _ _ _ . fill in the blanks more or much less or...

1. The explosion in technology has led to dramatic changes in how companies deliver training. The process of learning on the go in brief, accessible modules is starting to replace more traditional...

LO1 Define training and discuss why a strategic approach is important.

LO6 Provide an example for each of the four levels of training evaluation.