Soit G=(V,E) un graphe non-orienté et 2-arêtes connexe. Chaque arête et sommet de G est muni d'un poids. Le problème du sous-graphe 2-arêtes connexe de poids minimum dans G (2ECSP), est de trouver un sous-graphe 2-arêtes connexe de G tel que la somme des poids sur ses sommets et ses arête soit minimum. Le 2ECSP généralise le problème, bien connu, du sous-graphe Steiner 2-arêtes connexe. Dans cet article, l'enveloppe convexe des vecteurs d'incidences des solutions de 2ECSP est étudiée. Une formulation naturelle du problème par un programme linéaire en nombres entiers est premièrement établie. Il est aussi montré que la relaxation ne suffit pas pour décrire l'enveloppe convexe associée au 2ECSP même dans une classe restreinte comme celle des graphes série-parallèles. Une nouvelle classe d'inégalités valides pour le 2ECSP est introduite. Il est monté qu'une sous-classe de ces inégalités peut être séparée en temps polynomial. Comme conséquence, ces nouvelles inégalités peuvent être séparées en temps polynomial dans la classe des graphes série-parallèles.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by HAL in its series Working Papers with number
hal-00242945_v1.
Length: Date of creation: 2003 Date of revision: Handle: RePEc:hal:wpaper:hal-00242945_v1
Note: View the original document on HAL open archive server: http://hal.archives-ouvertes.fr/hal-00242945/en/ Contact details of provider: Web page: http://hal.archives-ouvertes.fr/
For technical questions regarding this item, or to correct its listing, contact: (CCSD).
Did you know? Citation analysis on IDEAS includes online papers that are freely accessible and whose text could be automatically analyzed, currently about 210000 papers.