Show simple item record

dc.contributor.authorBarahona, Francisco
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-04-13T10:07:18Z
dc.date.available2010-04-13T10:07:18Z
dc.date.issued1994
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3955
dc.language.isoenen
dc.subjectcompact systemsen
dc.subjectstable set polytopeen
dc.subjectcomposition of polyhedraen
dc.subjectPolyhedral combinatoricsen
dc.subject.ddc511en
dc.titleComposition of graphs and polyhedra III : Graphs with No $W_4$ minoren
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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.isversionofjnlnameSIAM Journal on Discrete Mathematics
dc.relation.isversionofjnlvol7en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate1994-05
dc.relation.isversionofjnlpages372-389en
dc.relation.isversionofdoihttp://dx.doi.org/10.1137/S089548019018268Xen
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSIAMen
dc.subject.ddclabelPrincipes généraux des mathématiquesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record