I have a weighted, undirected graph. I have a Minimum Spanning Tree for that graph. One edge (u,v), with weight w, is added to the graph.
How can I update the minimum spanning tree in O(V) time?
I think of it as adding an edge to the MST, and then deciding, in O(V) time, which edge has to then be removed.
Anyone have any ideas?