HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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 metadata

https://hal.inria.fr/inria-00151230
Contributor : Sylvain Soliman Connect in order to contact the contributor
Submitted on : Friday, June 1, 2007 - 6:41:51 PM
Last modification on : Wednesday, April 27, 2022 - 4:12:23 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

153

Files downloads

55