| dc.contributor.author | Barahona, Francisco | |
| dc.contributor.author | Mahjoub, Ali Ridha | |
| dc.date.accessioned | 2010-04-13T10:07:18Z | |
| dc.date.available | 2010-04-13T10:07:18Z | |
| dc.date.issued | 1994 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/3955 | |
| dc.language.iso | en | en |
| dc.subject | compact systems | en |
| dc.subject | stable set polytope | en |
| dc.subject | composition of polyhedra | en |
| dc.subject | Polyhedral combinatorics | en |
| dc.subject.ddc | 511 | en |
| dc.title | Composition of graphs and polyhedra III : Graphs with No $W_4$ minor | en |
| dc.type | Article accepté pour publication ou publié | |
| dc.description.abstracten | The authors characterize the stable set polytope for graphs that do not have a 4-wheel as a minor. The authors prove that the nontrivial facets are either "edge" inequalities or can be obtained by composing "odd cycles" and "subdivisions of $K_4 $." By adding some extra variables, it is shown that the stable set problem for these graphs can be formulated as a linear program of polynomial size. | en |
| dc.relation.isversionofjnlname | SIAM Journal on Discrete Mathematics | |
| dc.relation.isversionofjnlvol | 7 | en |
| dc.relation.isversionofjnlissue | 3 | en |
| dc.relation.isversionofjnldate | 1994-05 | |
| dc.relation.isversionofjnlpages | 372-389 | en |
| dc.relation.isversionofdoi | http://dx.doi.org/10.1137/S089548019018268X | en |
| dc.description.sponsorshipprivate | oui | en |
| dc.relation.isversionofjnlpublisher | SIAM | en |
| dc.subject.ddclabel | Principes généraux des mathématiques | en |
