0
$\begingroup$

It is known, that the problem of calculating Minimum Spanning Trees with an upper bound on the vertex degrees is NP complete.

Question:

what is the complexity of calculating Minimum Spanning Trees if the set of leaf nodes is given and all other vertex degrees must be greater than a given lower(!) bound $k$, under the condition that the underlying Graph is complete and symmetric and, that the existence of a spanning tree with the given degree constraints exists?

A concrete example would be to calculate a minimum spanning tree of a symmetric graph with $3*(2^n-1) + 1$ vertices of which $3*2^{n-1}$ are defined to be leaf nodes and all other verticex degrees are at least 3 in the spanning tree.

$\endgroup$

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.