9
$\begingroup$

The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead.

Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly more costly than an MST, but is the second cheapest? For example, if you switch one of the edges in this spanning tree, you end up with an MST and vice versa.

My question, though, is simply: How can I find the second cheapest spanning tree, given a graph $G$ with an MST?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The second cheapest path problem, called next-to-shortest path, is also interesting. $\endgroup$ – Bangye Oct 16 '14 at 13:00
  • $\begingroup$ The original title of this question was “Minimum to Maximum spanning trees?” That described the first paragraph of the post, which might be the original motivation for your question, but was not your question. When you post a question next time, please try to give it a title which describes your question. $\endgroup$ – Tsuyoshi Ito Oct 16 '14 at 23:36
  • 2
    $\begingroup$ IIRC, this is an exercise in CLRS. Voting to close. $\endgroup$ – Kaveh Oct 26 '14 at 1:49
  • $\begingroup$ Is it the process ? 1. Finding MST from a given graph. 2. removing the edge of maximum weight from the MST. 3. Then adding the edge in the MST from the given which weight is below the removing edge from the MST. $\endgroup$ – Remon Hasan Feb 11 '19 at 17:47
20
$\begingroup$

The second-smallest spanning tree differs from the minimum spanning tree by a single edge swap. That is, to get the second-smallest tree, you need to add one edge that's not already in the minimum spanning tree, and then remove the heaviest edge on the cycle that the added edge forms.

If you already have the minimum spanning tree, this can all be done in linear time. See e.g. V. King, "A simpler minimum spanning tree verification algorithm", Algorithmica 1997, doi:10.1007/BF02526037.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ How do you know that this is the second-smallest tree, rather than the 50.th smallest tree? $\endgroup$ – Taemyr Oct 15 '14 at 8:45
  • 6
    $\begingroup$ It's easy to prove yourself. But if you'd rather just look it up there's a proof in "A combinatorial ranking problem", Burns and Haff, Aeq. Math. 1976, dx.doi.org/10.1007/BF01835983 $\endgroup$ – David Eppstein Oct 15 '14 at 16:33
4
$\begingroup$

Could not add a comment due to lack of reputation.
As commented by David Eppstein you can find the proof of the fact that the second-smallest spanning tree differs from the minimum spanning tree by a single edge swap in the article "A combinatorial ranking problem", Burns and Haff.

Basically, in the article an algorithm is presented for finding an $n$th-best spanning tree of an edge-weighted graph $G$ with time $O(n)$.

And the link to read the paper for free is https://booksc.org/book/6732566/196389.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.