Question

Consider a minimum spanning tree for a weighted graph G= (V, E)and a new edge e,...

Consider a minimum spanning tree for a weighted graph G= (V, E)and a new edge e, connecting two existing nodes in V. Explain how to find a minimum spanning tree of the new graph in O(n)time, where n is the number of nodes in the graph. Prove correctness of the algorithm and justify the running time

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

After adding the new edge, we need to remove one edge from the new formed cycle in order to regain our minimum spanning tree. For this operation we will iterate over the new formed cycle and find the minimum weighted edge present in the cycle and delete the found edge.

This is correct because after deleteing the minimum weighted edge of the cycle, the cycle will break and also the egde deletion will lead to minimum weight beacause the edge chosen is the maximum weighted among all the edges present in the cycle.

The running time complexity of the algorithm is O(n) as we need to iterate once through the graph.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Consider an undirected graph G = (V, E) with an injective cost function c: E →...
Consider an undirected graph G = (V, E) with an injective cost function c: E → N. Suppose T is a minimum spanning tree of G for cost function c. If we replace each edge cost c(e), e ∈ E, with cost c'(e) = c(e)2 for G, is T still a minimum spanning tree of G? Briefly justify your answer.
Let T be a minimum spanning tree of graph G obtained by Prim’s algorithm. Let Gnew...
Let T be a minimum spanning tree of graph G obtained by Prim’s algorithm. Let Gnew be a graph obtained by adding to G a new vertex and some edges, with weights, connecting the new vertex to some vertices in G. Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T ? If you answer yes, explain how; if you answer no, explain why not.
Let e be the unique lightest edge in a graph G. Let T be a spanning...
Let e be the unique lightest edge in a graph G. Let T be a spanning tree of G such that e ∉ T . Prove using elementary properties of spanning trees (i.e. not the cut property) that T is not a minimum spanning tree of G.
A spanning tree of connected graph G = (V, E) is an acyclic connected subgraph (V,...
A spanning tree of connected graph G = (V, E) is an acyclic connected subgraph (V, E0 ) with the same vertices as G. Show that every connected graph G = (V, E) contains a spanning tree. (It is the connected subgraph (V, E0 ) with the smallest number of edges.)
Show that an edge e of a connected graph G belongs to any spanning tree of...
Show that an edge e of a connected graph G belongs to any spanning tree of G if and only if e is a bridge of G. Show that e does not belong to any spanning tree if and only if e is a loop of G.
Show that if an edge (u, v) is contained in some minimum spanning tree, then it...
Show that if an edge (u, v) is contained in some minimum spanning tree, then it is a least-weight edge in some cutset of the graph.
Which one of the following statements about Floyd's algorithm running on a graph with V nodes...
Which one of the following statements about Floyd's algorithm running on a graph with V nodes and E edges is correct? Group of answer choices The iterative (dynamic programming) version finds the shortest path between all pairs of nodes in time O(V3) The recursive version finds the transitive closure of a graph in O(3V) time. The iterative (dynamic programming) version finds the shortest path between all pairs of nodes in O(3E) time The iterative (dynamic programming) version always finds a...
Show Proof of correctness and state, and solve the Recurrence using the Master Theorem. Let G...
Show Proof of correctness and state, and solve the Recurrence using the Master Theorem. Let G = G(V, E) be an arbitrary, connected, undirected graph with vertex set V and edge set E. Assume that every edge in E represents either a road or a bridge. Give an efficient algorithm that takes as input G and decides whether there exists a spanning tree of G where the number of edges that represents roads is floor[ (|V|/ √ 2) ]. Do...
we consider a graph G= (V, E), with n=|V| and m=|E|. Describe an O(n+m) time algorithm...
we consider a graph G= (V, E), with n=|V| and m=|E|. Describe an O(n+m) time algorithm to find such a vertex w. Hint: a depth-first search from u might be helpful.
A Hamiltonian walk in a connected graph G is a closed spanning walk of minimum length...
A Hamiltonian walk in a connected graph G is a closed spanning walk of minimum length in G. PROVE that every connected graph G of size m contains a Hamiltonian walk of length at most 2m in which each edge of G appears at most twice.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT