Résumé
Given a graph with edge-costs, searching for a minimum cost structure that connects a subset of vertices is a classic problem. We examine the spanning problems under constraints on the vertex degrees. Spanning tree solutions were generally investigated to solve them. However, for some applications the solution is not necessarily a sub-graph. Assuming that the degree constraint is due to the limited instantaneous capacity of the vertex and that the only other constraint on the spanning structure is its connectivity, we propose a reformulation of some spanning problems. To find the optimal coverage of the concerned vertices, an extension of the tree concept has been proposed. A hierarchy is obtained by a graph homomorphism between a tree and a target graph. Since this spanning structure may refer vertices (and edges) of the target graph several times, it is more flexible to satisfy constraints and nevertheless pertinent for network applications. Hierarchies correspond to the optimal solutions of the new problems. Here we resume our first promising results on the degree-constrained spanning hierarchies. They can solve network related cases where trees meeting the constraints do not exist. In other cases, hierarchies outperform trees. Furthermore, the degree constrained spanning hierarchy problem can be approximated within a constant ratio (while it is not possible with trees).