Show simple item record

dc.contributor.authorBouchakour, Mustapha
dc.contributor.authorContenza, Teresa
dc.contributor.authorLee, C.W
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2009-10-05T14:34:39Z
dc.date.available2009-10-05T14:34:39Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2122
dc.language.isoenen
dc.subjectPolytopeen
dc.subject.ddc519en
dc.titleOn the dominating set polytopeen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversité Blaise Pascal, Clermont II;France
dc.contributor.editoruniversityotherUniversity of Kentucky;États-Unis
dc.contributor.editoruniversityotherMathematical Science Department, Otterbein College;États-Unis
dc.description.abstractenIn this paper, we study the dominating set polytope in the class of graphs that decompose by one-node cutsets where the pieces are cycles. We describe some classes of facets and procedures to construct facets of the polytope in that class of graphs, and establish some structural properties. As a consequence we obtain a complete description of the polytope by a system of inequalities when the graph is a cycle. We also show that the separation problem related to that system can be solved in polynomial time. This yields a polynomial time cutting plane algorithm for the minimum weight dominating set problem in that case. We further discuss the applications for the class of cactus graphs.en
dc.relation.isversionofjnlnameEuropean Journal of Combinatorics
dc.relation.isversionofjnlvol29en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2008
dc.relation.isversionofjnlpages652-661en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejc.2007.03.010en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProbabilités et mathématiques appliquéesen


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