I'm trying to think about an algorithm for this problem. I know there is an algorithm for the second cheapest MST in a graph, but if I understood it correctly it only solves cases in which every weight is singular. My question is how do I get the n'th (say 3rd) MST where duplicate weights count as same tree.

I thought about first applying prim's algorithm to get the MST, then given that such edge exists take the smallest out of the edges in G that are not in MST1, and then, because we create a circle, remove the maximum edge that is in the circle but still smaller than the edge we added. I believe it will take linear time. Am I on the right direction?

  • $\begingroup$ So, is $n$ the number of vertices? If yes, then it is same as maximum spanning tree. If you meant some constant, we can start working on it. First, can you give some reference to the algorithm of MST you have in mind? I am aware of a cubic time(over vertices) algorithm for that which makes no assumptions. $\endgroup$ – User Not Found Jan 7 '18 at 14:14
  • 1
    $\begingroup$ I think this is relevant to your question H.N. Gabow, Two Algorithms for Generating Weighted Spanning Trees in Order, SIAM J. Comput. 6, 1977, 139–150. epubs.siam.org/doi/pdf/10.1137/0206011 $\endgroup$ – Ameer Jewdaki Jan 7 '18 at 19:59

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.