Abstract
In this study, the constrained spanning problem supposing heterogeneous degree bounds on nodes capacities representing limited momentary capacities is analyzed. Given an undirected graph, we suppose different positive integer upper bounds associated with nodes to limit their degree for each visit. Finding the minimum cost connected spanning structure satisfying the degree constraints is the subject of our work. Usually, for budget constrained problems spanning trees are the solutions and the problem is NP hard which can not be approximated by a constant factor. Moreover, spanning the nodes with a tree respecting the degree constraints is not always possible. We demonstrate that the optimal solution to solve the capacity limited spanning problem with heterogeneous bounds can be different from a spanning tree, and an earlier proposed generalization of the tree concept, i.e. the hierarchy corresponds to the minimum cost solution. We investigate on the degree constrained minimum spanning hierarchy (DCMSH) under non-uniform constraints, on the conditions of its existence and on the possibility of its approximation being the problem NP hard. We prove necessary and sufficient conditions to find spanning hierarchies corresponding to the constraints.