Design an algorithm to update the minimum spanning tre

Assignment Help Computer Engineering

Reference no: EM132141244

Suppose 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 e is increased.

• Design an algorithm to update the minimum spanning tree when the weight of a single edge e is decreased.

In both cases, the input to your algorithm is the edge e and its new weight; your algorithms should modify T so that it is still a minimum spanning tree. Analyze the running time of your algorithms and prove the correctness.

Reference no: EM132141244

Questions Cloud

Create an algorithm for telling if l and m store the same : Create an algorithm for telling if L and M store the same sequence of elements (but perhaps with different starting points).

Provide again a polynomial time algorithm : Suppose we are given a directed graph G = (V, E), a set of nodes A V (denoted as people) and a set of nodes B V (denoted as exit).

What is the running time of your algorithm : Give a bottom-up dynamic programming algorithm based off your recursive definition. What is the running time of your algorithm?

How many total packets are sent with stop-and-wait : Assume that ACKs are never lost. How many total packets (including retransmissions) are sent with stop-and-wait.

Design an algorithm to update the minimum spanning tre : Design an algorithm to update the minimum spanning tree when the weight of a single edge e is increased.

What speedup is possible with pipelining : What is the maximum execution rate without pipelining? What speedup is possible with pipelining?

Would there be any advantages to using the cts and rts frame : Suppose the IEEE 802.11 RTS and CTS frames were as long as the standard DATA and ACK frames.

How does the behavior of dbscan and k-means differ on : Suppose you are given two sets of 100 points that fall within the unit square. One set of points (a) is arranged so that the points are uniformly spaced.

Describe a linear time algorithm for this does di-graph g : Determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem).

User Account

All Pages