Second Best MCST

Revision en1, by binary_eagle, 2015-08-09 14:03:16

Hi guys,

I have done some thinking about how to solve 2nd best Minimum Spanning Tree. I want to hear your suggestions on if its correct and how you would solve it. Thanks.

Let G = (V,E) be a graph. Lets assume we know how to solve the MST using Kruskal as that is trivial. At each step of Kruskal, consider an edge e=<a,b>.

If e does not cause a cycle then it is in MST Otherwise It can cause a cycle. Now consider all edges in such a cycle and take the biggest edge in the cycle e1.

Claim : If we maintain the value (e-e1) and minimize it over all cases where adding an edge will introduce a cycle then we would have the 2nd best MST by simply replacing e1 with e.

Is this true ? How would you solve this problem ?

Thanks.

Tags graph, mst, kruskal, spanning tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English binary_eagle 2015-08-09 14:03:16 762 Initial revision (published)