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.
Complete list of metadatas

https://hal.inria.fr/inria-00085802
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 2:10:49 PM
Last modification on : Friday, June 22, 2018 - 9:32:45 AM
Long-term archiving on : Tuesday, April 6, 2010 - 12:09:34 AM

File

Identifiers

  • HAL Id : inria-00085802, version 1

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. ⟨inria-00085802⟩

Share

Metrics

Record views

253

Files downloads

232