Show simple item record

dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorMailfert, Jean
dc.date.accessioned2010-03-16T08:14:13Z
dc.date.available2010-03-16T08:14:13Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3694
dc.language.isoenen
dc.subjectPolynomial time separation algorithmen
dc.subjectGraphen
dc.subjectPolytopeen
dc.subject.ddc003en
dc.titleOn the independent dominating set polytopeen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper, we consider the independent dominating set polytope. We give a complete linear description of that polytope when the graph is reduced to a cycle. This description uses a general class of valid inequalities introduced in [T.M. Contenza, Some results on the dominating set polytope, Ph.D. Dissertation, University of Kentucky, 2000]. We devise a polynomial time separation algorithm for these inequalities. As a consequence, we obtain a polynomial time cutting plane algorithm for the minimum (maximum) independent dominating set problem on a cycle. We also introduce a lifting operation called twin operation, and discuss some polyhedral consequences. In particular, we show that the above results can be extended to a more general class of graphs.en
dc.relation.isversionofjnlnameEuropean Journal of Combinatorics
dc.relation.isversionofjnlvol27en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2006-05
dc.relation.isversionofjnlpages601-616en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejc.2004.07.015en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


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