Partitionnement de graphes par des arbres sous contraintes de degré

Résumé : Nous présentons une contrainte de partitionnement de graphe par des arbres sous contraintes de degré. Étant donné un graphe orienté G, la contrainte spécifie que toute solution est formée par N arbres, tels que le nombre de fils d'un sommet quelconque de G appartienne à un ensemble donné de valeurs. Il existe pour la contrainte d'arbre pure, introduite dans [2], une caractérisation complète polynomialement évaluable. Cependant, la prise en compte du nombre de fils de chaque sommet rend le problème d'existence d'une solution NP-complet. Nous montrons donc comment intégrer une relaxation polynomiale de la contrainte de degré, prenant en compte les différents aspects de la contrainte d'arbre pure. Enfin, nous présentons une première série de résultats partiels pratiques sur les problèmes (NP-complets) d'existence d'un chemin Hamiltonien et d'un arbre binaire couvrant dans le cas de graphes orientés quelconques.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00085802
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 14:10:49
Dernière modification le : jeudi 5 avril 2018 - 10:36:25
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:09:34

Fichier

Identifiants

  • HAL Id : inria-00085802, version 1

Collections

Citation

Nicolas Beldiceanu, Pierre Flener, Xavier Lorca. Partitionnement de graphes par des arbres sous contraintes de degré. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085802〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

209