Given a weighted complete graph (or more exactly, a matrix of pairwise metric distances between vertices), I need to find a good approximation of the binary spanning tree of lowest total cost.

There are a lot of good methods to find the MST, and a few heuristics to find a degree-constrained MST. But the latter are for any degree and pretty heavy to implement and run.

Is there might be some good heuristics for the special case where the degree is 2 and the graph is complete…

(I'm more concerned with easiness of implementation/speed than optimality)

Bonus question: my goal is actually to get a radius-constrained MST (in the hope of solving the apparently too complex task of finding a graph/tree's "backbone")… A binary MST seems like it would give me a good approximation (or at least a warm start for local optimisation). Does my intuition make sense?


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.