Show simple item record

Complexity of the satisfactory partition problem

dc.contributor.authorBazgan, Cristina
dc.contributor.authorTuza, Zsolt
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2010-04-12T13:41:51Z
dc.date.available2010-04-12T13:41:51Z
dc.date.issued2003
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3937
dc.language.isoenen
dc.subjectGraph
dc.subjectComplexity
dc.subjectPolynomial Algorithm
dc.subjectNP-complete
dc.subjectSatisfactory partition
dc.subject.ddc003en
dc.titleComplexity of the satisfactory partition problem
dc.typeDocument de travail / Working paper
dc.description.abstractenThe Satisfactory Partition problem consists in deciding if a given graph has apartition of its vertex set into two nonempty parts such that each vertex has at least asmany neighbors in its part as in the other part. This problem was introduced by Gerberand Kobler [GK98, GK00] and further studied by other authors but its complexity remained open until now. We prove in this paper that Satisfactory Partition, as wellas 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 knonempty parts (k ≥ 3) is requested.
dc.identifier.citationpages13
dc.relation.ispartofseriestitleNote de recherche du LAMSADE
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-05T15:24:04Z


Files in this item

Thumbnail
Name:
notedeR34.pdf
Size:
281.8Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record