1

We have a Minimum Spanning Tree of a graph that was created using the Kruskal Algorithm. We are supposed to add a new node to this graph. The connections and their values of this node are also known to us. We're asked to provide an algorithm that adds this new node to the MST too.

My first thought were: "Isn't the answer simply "Connect the new node to the nearest (the one it is connected to with the lightest connection) node available?"".

But then I realised that this wouldn't work in a situation like this one: A graph has nodes A and B connected by an edge with weight 100. The MST of this graph just contains this singular edge. Node C is added with an edge to A with weight 1 and an edge to B with weight 2. Simply adding the smallest edge adjacent to C to the the MST gives you a spanning tree with weight 101, where it is evident that the MST of this new graph should have weight 3.

So, what is the required algorithm here?

  • 1
    There is already a solution here http://stackoverflow.com/questions/9811863/dynamic-minimum-spanning-tree. Your question is "Maintaining Minimum Spanning Trees in Dynamic Graphs". – Shridhar R Kulkarni May 21 '17 at 02:39
  • There is an algorithm that solves this in quadratic time, but best achievable time is O(nlogn) only. – Sumeet May 21 '17 at 06:58
  • Do you need to add just one node? If it's the case, you can ignore the fact that MST already exists and just find an MST a new graph. I'd recommend to use this method in any case, unless it's too slow. – kraskevich May 21 '17 at 13:16

0 Answers0