On the Approximation of Degree Constrained Spanning Problems in Graphs under Non Uniform Capacity Constraints
Sur l'approximation des problèmes de recouvrements de graphes sous non uniformes contraintes sur les nœuds
Résumé
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.
Dans notre étude, le problème de recouvrement de coût minimum sous contraints supposant des bornes hétérogènes sur les capacités de nœuds est analysé. Les degrés représentent des capacités momentanées. Dans un graphe non orienté, nous supposons différentes bornes supérieures positifs associés aux nœuds pour limiter leur degré à chaque visite. Trouver la structure connectée à coût minimum satisfaisant les contraintes de degré est le sujet de notre travail. Habituellement, si les contraintes sont budgétaires, les arbres couvrants sont les solutions et le problème est NP-difficile qui ne peut pas être approximé par un facteur constant. De plus, couvrir les nœuds avec un arbre respectant les contraintes de degré n'est pas toujours possible. Nous démontrons que la solution optimale pour résoudre le problème de recouvrement sous contraintes de capacités hétérogènes peut être différente d'un arbre. Une généralisation des arbres proposée antérieurement qu'on a baptisé "hiérarchie" correspond à la solution de coût minimum. Nous étudions la hiérarchie minimale sous contrainte de degré avec des contraintes non uniformes, les conditions de son existence et la possibilité de son approximation.
Origine : Fichiers produits par l'(les) auteur(s)