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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00151230
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 6:41:51 PM
Last modification on : Friday, June 22, 2018 - 9:34:07 AM
Long-term archiving on : Thursday, April 8, 2010 - 6:45:13 PM

File

41.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

238

Files downloads

104