the euclidean degree-4 minimum spanning tree problem is np-hard
We show that it is an NP-hard problem to decide for a given set P of n points in the Euclidean plane and a given parameter k?R, whether P admits a spanning tree of maximum vertex degree four whose sum of edge lengths does not exceed k.
spanning trees degree-constricted graphs degree-restricted graphs geometric graphs geometric optimization np-complete reduction bounded-degree graphs