Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorTuza, Zsolt
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2010-03-09T14:51:06Z
dc.date.available2010-03-09T14:51:06Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3676
dc.language.isoenen
dc.subjectPolynomial algorithmen
dc.subjectComplexityen
dc.subjectGraphen
dc.subjectSatisfactory partitionen
dc.subject.ddc511en
dc.titleThe satisfactory partition problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe SATISFACTORY PARTITION problem consists in 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 [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283–291] and further studied by other authors but its complexity remained open until now. We prove in this paper that SATISFACTORY PARTITION, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (kgreater-or-equal, slanted3) is requested.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol154en
dc.relation.isversionofjnlissue8en
dc.relation.isversionofjnldate2006-05
dc.relation.isversionofjnlpages1236-1245en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2005.10.014en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
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