CODEWITHSUNDEEP
algorithmgraphcomputer-science
Elimination
Elimination

Reputation: 2723

Update an MST after removing 3 edges from the graph

Let G(V,E) an undirected and connected graph with the weight function w. We are given T, an MST of G. Now we remove e1, e2, e3 from G (which also appear in T) and get a new graph, G'. Describe an efficient algorithm to find an MST of G'.

My intuition tells me that we can throw those 3 edges and run Prim algorithm for G' starting from T-{e1, e2,e3}.

Is my intuition correct? Could help me formulate this (Or suggest another approach)?

Upvotes: 1

Views: 87

Answers (2)

marvel308
marvel308

Reputation: 10458

You can solve it using Kruskal's Algorithm where you start traversing the edges which have a weight >= max(e1,e2,e3) from the set { S-{e1,e2,e3} }. Before this step the graph would have all the edges you need.

Upvotes: 1

asp
asp

Reputation: 172

Prim's algorithm grows a tree T in G from a single vertex by adding edges, but removing an edge from T makes it disconnected, so you cannot use this as partial input for the algorithm.

You can however use Kruskal's agorithm, which grows a forest T until it is connected. Deleting one edge of T from the G requires one new step of the algorithm. The proof is along the lines of the proof of correctness for the algorithm itself.

Upvotes: 1

Related Questions