Show simple item record

dc.contributor.authorBarahona, Francisco
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-01-05T11:14:57Z
dc.date.available2010-01-05T11:14:57Z
dc.date.issued1994
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2805
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 II : Stable Setsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenA graph $G$ with a two-node cutset decomposes into two pieces. A technique to describe the stable set polytope for $G$ based on stable set polytopes associated with the pieces is studied. This gives a way to characterize this polytope for classes of graphs that can be recursively decomposed. This also gives a procedure to describe new facets of this polytope. A compact system for the stable set problem in series-parallel graphs is derived. This technique is also applied to characterize facet-defining inequalities for graphs with no $K_5 \backslash e$ minor. The stable set problem is polynomially solvable for this class of graphs. Compositions of $h$-perfect graphs are also studieden
dc.relation.isversionofjnlnameSIAM Journal on Discrete Mathematics
dc.relation.isversionofjnlvol7en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate1994
dc.relation.isversionofjnlpages359-371en
dc.relation.isversionofdoihttp://dx.doi.org/10.1137/S0895480190182678en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSociety for Industrial and Applied Mathematicsen
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