Condition nécessaire pour la contrainte de partitionnement de graphes par des chemins

Résumé : Etant donné un graphe orienté $\cG$, le problème des $\NPATH$-chemins disjoints consiste à trouver une partition de $\cG$ en $\NPATH$ chemins noeuds-disjoints, tel que chaque chemin termine sur un noeud appartenant à un sous-ensemble des noeuds de $\cG$. Cet article fournit une condition nécessaire, pour le problème des $\NPATH$-chemins disjoints, combinant (1) la structure du graphe réduit associé au graphe $\cG$, (2) la structure de chaque composante fortement connexe de $\cG$ vis à vis des relations de dominance entre les noeuds de $\cG$, et (3) la structure des connexions entre les composantes fortement connexes de $\cG$. Finalement, nous montrons comment exploiter cette condition nécessaire pour en dériver une contrainte de partitionnement de graphes par des chemins.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt / France, 2007, JFPC07
Liste complète des métadonnées

https://hal.inria.fr/inria-00151230
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:41:51
Dernière modification le : vendredi 22 juin 2018 - 09:34:07
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:45:13

Fichier

41.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151230, version 1

Citation

Nicolas Beldiceanu, Xavier Lorca. Condition nécessaire pour la contrainte de partitionnement de graphes par des chemins. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt / France, 2007, JFPC07. 〈inria-00151230〉

Partager

Métriques

Consultations de la notice

228

Téléchargements de fichiers

89