Question: Q1) You are given a weighted undirected graph G(V, E) and its MST T(V, E). Now suppose an edge (a, b) E has been deleted

Q1) You are given a weighted undirected graph G(V, E) and its MST T(V, E). Now suppose an edge (a, b) E has been deleted from the graph. You need to devise an algorithm to update the MST after deletion of (a, b). Describe an algorithm for updating the MST of a graph when an edge (a, b) is deleted from the MST (and the underlying graph). Its time complexity must be better than running an MST algorithm from scratch. State and explain the time complexity of your algorithm. Analyze time complexity of your algorithm. You can assume that all edge weights are distinct, that the graph has E edges and V vertices after the deletion, that the graph is still connected after the deletion of the edge, and that your graph and your MST are represented using adjacency lists.

Q2) Can you use the DFS algorithm to compute the number of distinct paths between two given nodes, s and t? Two paths are considered distinct if they differ by 1 or more edges. If you think the answer is yes, then provide the pseudo-code for a DFS based algo that computes this number in O(|V|+|E|). If you think the answer is no, draw a graphwith eight vertices in total,with two of its vertices labeleds and t, in which DFS will fail to compute the number of distinct pathsbetween s and t.

Q3) CM of Punjab has decided to build a new road in Lahore. He has a choice of k roads from which he can only build one. However, secretly, CM is only interested in two places in the city: s and t (his office and home). He wishes to build the road which, when added into the city, reduces the cost of the shortest path from s to t the most. He has hired you to write a computer program to tell him which of the k roads to build for this purpose. The input to your program is going to be a directed weighted graph and list of k weighted edges not already in the graph.

(a)Write an algorithm that does the job in O(k(|E|)lg|V|).Note that since k itself is O(|V|2 )this is a pretty slow algorithm.

(b) CM is in a hurry. He wants you to write an algorithm that works in O (k+|E|lg|V|), only. Can you do it?

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!

S 2 Problem 1 (10 points]: Consider the following problem denoted WSP opt, defined as follows: Given a weighted undirected graph G = (V, E, w) and two vertices s and t where the ) weight of edge e is...

It might be very helpful if anyone can answer one of theseThanks 1. Given a simple, undirected graph G- (V, E), a square is four edges of the form (u, v), (v, w), (w, u), where u, v, w E V. Consider...

Please help with the following questions: Q1.4 4 Points = Consider a connected undirected graph G (V, E) with nonnegative edge weights w. Now suppose each edge weight is increased by 1: w'(u, v) =...

Lets go back to the original motivation for the Minimum Spanning Tree Problem. We are given a connected, undirected graph G = ( V , E ) with positive edge lengths {l e }, and we want to find a...

Sometimes, it's good to have alternatives. Supposed you've just moved to a new city. You want to select an apartment that has the larget number of distinct shortest paths to your workplace. Since...

A text file describing the graph in Fig. 1 is given below: 5 1, 10 8, 10 10,8 7,4 3,1 0,1,10 1,2,5 2,3,25 0,3,3 3,4,8 VO V4 10 V3 VI S Figure 1: Example of a weighted undirected graph.

A particular part in a car engine expands as the engine warms up to operating temperature, but the amount of expansion depends on the metal from which the part is made. Rank the following metals from...

Three hours ago, it was -5F. If the temperature has increased by 9F in the last three hours, what is the current temperature?

For absolute purchasing power parity to hold: a . The International Fisher effect must exist. b . The unbiased forward rate theory must be observable. c . Transaction costs must be zero. d . The...

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...

Question What are the alternatives to the classic employer-paid long-term disability plan?

Question Is there any type of disability plan that provides both employer payment of deductible premiums and non-taxation of benefits to the employee?

Question Is there ever any advantage in designing an HRA that discriminates by covering only specific executives?