Minimal spanning trees with a constraint on the number of leaves

In this paper we discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized terminal networks. The constraint on the number of leaves arises because the software and hardware associated with each terminal differs according to its position in the tree. Usually, the software and hardware associated with a ‘degree-1’ terminal is cheaper than the software and hardware used in the remaining terminals because for any intermediate terminal j one needs to check if the arrival message is destined to that node or to any other node located after node j. As a consequence, that particular terminal needs software and hardware for message routing. On the other hand, such equipment is not needed in ‘degree-1’ terminals. Assuming that the hardware and software for message routing in the nodes is already available, the above discussion motivates a constraint stating that a tree solution has to contain exactly a certain number of ‘degree-1’ terminals. We present two different formulations for this problem and some lower bounding schemes derived from them. We discuss a simple local-exchange heuristic and present computational results taken from a set of complete graphs with up to 40 nodes. Integer Linear Programming formulations for related problems are also discussed at the end.