CODEWITHSUNDEEP
algorithmgraphtreeruntimebig-o
James the Great
James the Great

Reputation: 951

Update minimum spanning tree if edge is removed

I am having trouble with the following question:

Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly.

An edge is removed from G to produce a new graph such that the new graph is still connected. Give an algorithm that uses T to find a minimum spanning tree for the new graph in O(|E|) time.

Upvotes: 1

Views: 2045

Answers (1)

lmcphers
lmcphers

Reputation: 468

Since everything is still connected and only one edge has been removed, then most (and maybe all) of the spanning tree remains the same. Attempt to construct the same minimum spanning tree, and if the edge that was removed was part of the spanning tree, grab the next smallest edge that completes the minimum spanning tree.

Upvotes: 1

Related Questions