Give an algorithm to update the mst when the weight

Assignment Help Computer Engineering

Reference no: EM132154710

Updating Minimum Spanning Trees

Let G be an edge-weighted, undirected, and connected graph. You are already given the MST, T, of G.

Give an algorithm to update the MST when the weight of a single edge e ? G is increased, producing a new graph G0 .

Specifically, the input is the edge e and its new weight, and your algorithm should modify T so that it is an MST in G0 , and do so in O(|V | + |E|) time. Useful Fact from class: The min weight edge across any vertex bi-partition must be in the MST.

Moreover, (the removal of) any edge e in the MST induces a bi-partition, call it B(e), and so e must be the minimum weight edge across B(e). A rigorous proof is not required though please explain your answer.

Reference no: EM132154710

Questions Cloud

What else must be true of such a program for there : In UNIX or Linux systems, it is generally considered an unsafe practice to have executable files that are set UID to "root" because.

How much is the opportunity coast under the current policy : a. How much is the opportunity coast under the current policy? b. How much are the trading cost and total cost?

What was shelly mortality and expense risk charge for year : Her account value during the year is $90,000. What was Shelly's mortality and expense risk charge for the year?

Write the constructor method : Write the constructor method, init (self, acctNum acctName, acctBal) which creates an account with the given values for the instance variables.

Give an algorithm to update the mst when the weight : Let G be an edge-weighted, undirected, and connected graph. You are already given the MST, T, of G.

What was the surrender charge sophia had to pay : Assume that the contract value had not increased or decreased because of investment performance. What was the surrender charge Sophia had to pay?

What is the project irr : The cost of capital is 13%. What is the project's IRR?

Create a program that maintains a list of employees : Create a program that maintains a list (an array) of employees. The user should be able to add employees to the list.

What is the future value at the end of year : What is the future value at the end of year 15 of $10,000 deposited today into an account that pays interest of 4.5% p.a., but with monthly compounding?

User Account

All Pages