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


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.


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.