A note on the Chvátal rank of clique family inequalities
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PECHER, Arnaud | |
| hal.structure.identifier | Institute for Mathematical Optimization [IMO] | |
| dc.contributor.author | WAGLER, Annegret K. | |
| dc.date.accessioned | 2024-04-04T02:48:11Z | |
| dc.date.available | 2024-04-04T02:48:11Z | |
| dc.date.created | 2007 | |
| dc.date.issued | 2007 | |
| dc.identifier.issn | 0399-0559 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191716 | |
| dc.description.abstractEn | Clique family inequalities , form an intriguing class of valid inequalities for the stable set polytopes of all graphs. We prove firstly that their Chvátal-rank is at most a, which provides an alternative proof for the validity of clique family inequalities, involving only standard rounding arguments. Secondly, we strengthen the upper bound further and discuss consequences regarding the Chvátal-rank of subclasses of claw-free graphs. | |
| dc.language.iso | en | |
| dc.publisher | EDP Sciences | |
| dc.title.en | A note on the Chvátal rank of clique family inequalities | |
| dc.type | Article de revue | |
| dc.subject.hal | Informatique [cs]/Autre [cs.OH] | |
| bordeaux.journal | RAIRO - Operations Research | |
| bordeaux.page | 289--294 | |
| bordeaux.volume | 41 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00307758 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00307758v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=RAIRO%20-%20Operations%20Research&rft.date=2007&rft.volume=41&rft.spage=289--294&rft.epage=289--294&rft.eissn=0399-0559&rft.issn=0399-0559&rft.au=PECHER,%20Arnaud&WAGLER,%20Annegret%20K.&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||