Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorTuza, Zsolt
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2010-04-12T12:35:22Z
dc.date.available2010-04-12T12:35:22Z
dc.date.issued2010
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3928
dc.language.isoenen
dc.subjectDegree constraints
dc.subjectApproximation algorithm
dc.subjectVertex partition
dc.subjectCombinatorial optimization
dc.subjectComplexity theory
dc.subject.ddc003en
dc.titleSatisfactory graph partition, variants, and generalizations
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe Satisfactory Partition problem asks for deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [M. Gerber, D. Kobler, Algorithmic approach to the satisfactory graph partitioning problem, European Journal of Operational Research 125 (2000) 283–291] and studied further by other authors. In this paper we first review some applications and related problems. Then, we survey structural, complexity, and approximation results obtained for Satisfactory Partition and for some of its variants and generalizations. A list of open questions concludes this survey.
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol206
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages271-280
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2009.10.019
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-10-06T09:42:16Z


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