So in our class, we did a proof on Kruskal's algorithm for finding Minimum Spanning Tree. Now, based on that, I have to modify it to find me a Maximum Spanning Tree. I know the idea, taking maximum-cost edges. I also have an idea why this works, because taking maximum edge from the remaining set is just like taking minimum edge from the same graph but with negative weights. My trouble is, I have no idea how to formally write down the proof knowing that Kruskal's algorithm is correct for finding Minimum spanning tree. Can someone help me and say whether I am right, and how I should write this formally, by not having to repeat the whole proof for MST and change a few things? Thanks!

  • $\begingroup$ Kruskal's algorithm does work directly for negative weights. Why can't you just apply it, as it is, but on the graph obtained by negating the edges? $\endgroup$ – Clement C. Mar 26 '15 at 19:28
  • $\begingroup$ That was my point. The assumption was that weights are positive. So what should I write down? $\endgroup$ – Luka Bulatovic Mar 26 '15 at 19:29
  • $\begingroup$ Well, exactly this. Since Kruskal's algorithm (Minimum Spanning Tree) works for negative weights as well, use is to compute a Minimum Spanning Tree of the negated-weight graph. This will be a maximum spanning tree of the original graph. $\endgroup$ – Clement C. Mar 26 '15 at 19:30
  • $\begingroup$ Okay, I get that. I am just confused because it says: describe the algorithm and prove it. Notice: modify some of the known algorithms for MSTs. So is this an actual proof? :S $\endgroup$ – Luka Bulatovic Mar 26 '15 at 19:32
  • 1
    $\begingroup$ It is, as long as you explain why "MinST of negated tree $\Leftrightarrow$ MaxST of original", and state clearly that/why Kruskal's algorithm also works for negative weights. $\endgroup$ – Clement C. Mar 26 '15 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.