On Non-Rank Facets in Stable Set Polytopes of Webs with Clique Number Four
| 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 | 2006-06 | |
| dc.date.issued | 2006-06 | |
| dc.identifier.issn | 0166-218X | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191717 | |
| dc.description.abstractEn | Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number ≤ 3 have rank facets only while there are examples with clique number > 4 having non-rank facets. The aim of the present paper is to treat the remaining case with clique number =4: we provide an infinite sequence of such webs whose stable set polytopes admit non-rank facets | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.title.en | On Non-Rank Facets in Stable Set Polytopes of Webs with Clique Number Four | |
| dc.type | Article de revue | |
| dc.subject.hal | Informatique [cs]/Autre [cs.OH] | |
| bordeaux.journal | Discrete Applied Mathematics | |
| bordeaux.page | 1408--1415 | |
| bordeaux.volume | 154 | |
| 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-00307757 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00307757v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Discrete%20Applied%20Mathematics&rft.date=2006-06&rft.volume=154&rft.spage=1408--1415&rft.epage=1408--1415&rft.eissn=0166-218X&rft.issn=0166-218X&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. |
|||