CODEWITHSUNDEEP
algorithmgraph-algorithm
user2463517
user2463517

Reputation: 197

New MST resulting from multiple edge weights being reduced?

We know the original graph and the original MST. Now we change k edge weights in the graph. Is there any way we can generate the new MST from the old graph in O((n + k) log n) time?

Upvotes: 1

Views: 183

Answers (1)

wookie919
wookie919

Reputation: 3134

  • Start with the original MST.
  • Add to the MST all edges that had their weights reduced. If the edge was already in the original MST, then just leave it there with the edge weight reduced.
  • Let this new resulting graph be G.
  • Solve MST on G.

MST can be solved in O(mlogn) time where m is the number of edges and n is the number of vertices in the graph.

Since G has O(n + k) edges, you can find the new MST in O((n+k)logn) time.

Upvotes: 1

Related Questions