dc.contributor.author Bazgan, Cristina dc.contributor.author Tuza, Zsolt dc.contributor.author Vanderpooten, Daniel dc.date.accessioned 2010-03-09T14:51:06Z dc.date.available 2010-03-09T14:51:06Z dc.date.issued 2006 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/3676 dc.language.iso en en dc.subject Polynomial algorithm en dc.subject Complexity en dc.subject Graph en dc.subject Satisfactory partition en dc.subject.ddc 511 en dc.title The satisfactory partition problem en dc.type Article accepté pour publication ou publié dc.description.abstracten The 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.isversionofjnlname Discrete Applied Mathematics dc.relation.isversionofjnlvol 154 en dc.relation.isversionofjnlissue 8 en dc.relation.isversionofjnldate 2006-05 dc.relation.isversionofjnlpages 1236-1245 en dc.relation.isversionofdoi http://dx.doi.org/10.1016/j.dam.2005.10.014 en dc.description.sponsorshipprivate oui en dc.relation.isversionofjnlpublisher Elsevier en dc.subject.ddclabel Principes généraux des mathématiques en
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.