Abstract
Degree constrained spanning tree problems are known and deeply analyzed when the graph nodes are provided with limited budgets. We examine the constrained spanning problem supposing heterogeneous degree bounds on nodes representing limited momentary capacities. In an undirected graph, different positive integer upper bounds are associated with nodes to limit their degree for each visit. The exact formulation of finding the minimum cost connected spanning structure satisfying these degree constraints is the subject of our work. The capacity constrained spanning problem with homogeneous constraints has been solved using spanning hierarchies which can be different from spanning trees. Here the case with non uniform constraints is analyzed, and we present an ILP based solution to this NP hard problem. The gain of applying hierarchies is demonstrated running ILPs for hierarchies and trees.