0

I am trying to update a MST by adding a new vertex in the MST. For this, I have been following "Updating Spanning Tree" by Chin and Houck. http://www.computingscience.nl/docs/vakken/al/WerkC/UpdatingSpanningTrees.pdf

A step in the paper requires me to find the largest edge in the path/paths between two given vertices. My idea is to find all the possible paths between the vertices and then, subsequently find the largest edge from the paths. I have been trying to implement this in MATLAB. However, so far, I have been unsuccessful. Any lead / clear algorithm to find all paths between two vertices or even the largest edge in the path between two given nodes/ vertices would be really welcome.

For reference, I would like to put forward an example. If the graph has following edges 1-2, 1-3, 2-4 and 3-4, the paths between 4 and 4 are:

1) 4-2-1-3-4

2) 4-3-1-2-4

Thank you

slowhead
  • 5
  • 5

1 Answers1

0

The algorithm works by lowering the t value to exclude large edges from the new MST. When the algorithm completes, t will be the lowest edge that remains to be inserted to complete the MST.

The m value represents the largest edge on a path from r to z, local to each run of INSERT. m is lowered at each iteration of the loop if possible, thereby removing the previous m edge as a possible candidate for t.

It's not easy to explain in words, I recommend doing a run of the algorithm on paper until the steps are clear.

I made a quick attempt to sketch the steps here: http://jacob.midtgaard-olesen.dk/?p=140

But basically, the algorithm adds edges from the old MST unless it finds a smaller edge to add between the new node z and another node in the old MST. In the example, the edge (A,B) is not in the new tree, since a better connection to B was found by the algorithm.

Note that on selecting h and k, if t and (w,r) have equal edge value, I believe you should choose (w,r)

Finally you should probably go trough the proof following the algorithm to understand why the algorithm works. (I didn't read it all :) )

Jacob Midtgaard-Olesen
  • 161
  • 4
  • I deleted my first answer as my interpretation of m was wrong. I hope you find the example helpful. If you need more help I can read through the proof later. But as I noted in the other answer, you are not supposed to find the largest edge, the algorithm does that by itself. – Jacob Midtgaard-Olesen Jul 15 '12 at 21:57
  • Thank you very much Jacob Midtgaard-Olesen. I really appreciate your help – slowhead Jul 16 '12 at 07:02
  • If my answer was sufficient for you to get the algorithm going you should probably mark the answer as accepted. :) – Jacob Midtgaard-Olesen Jul 16 '12 at 16:24
  • I am working on the algorithm. I will surely do that once I get it right :) Either way, it has helped me to keep going. I hope to get it right soon. – slowhead Jul 16 '12 at 16:31