Problem 5 Updating Minimum Spanning Trees (12 points) Problem 6b in Chapter 20 o

Question

Problem 5 Updating Minimum Spanning Trees (12 points) Problem 6b in Chapter 20 of Jeff's notes: 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 E G is increased, producing a new graph G. Specifically, your are given the edge e and its new weight, and your algorithm should modify T so that it is an MST in G', and do so in O(V El) 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 defines a vertex bi-partition, call it B(e), and as e is the only edge from the MST which goes across B(e), e must be the minimum weight edge across B(e) in G.

Explanation / Answer

Find_MST(Graph G, MST T)

Update weight of an edge e(u,v) by increasing it.

Old_cost? Cost(u,v)

if (edge e is not in MST (by checking parents of vertex v to vertex u in MST)

then there is no change in MST return cost(MST).

min? Cost(u,v)

edge ?e(u,v)

for each edge e’(v,wi) in adjacency list start from v

if(cost(e’)<min and e’ is not in MST)

min? cost(e’)

edge ? e’(v,wi)

if(edge is not e(u,v))

then remove e from MST and update parents v and cost of MST

MST ?MST- Old_cost + cost(e’)

Parent(v) ?wi

                                     

else update cost of MST

MST ?MST- Old_cost + Cost(u,v)

return cost(MST)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.