Show simple item record

Approximation of satisfactory bisection problems

dc.contributor.authorBazgan, Cristina
dc.contributor.authorTuza, Zsolt
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2010-01-12T14:41:19Z
dc.date.available2010-01-12T14:41:19Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2904
dc.language.isoenen
dc.subjectApproximation algorithmen
dc.subjectNP-completeen
dc.subjectComplexityen
dc.subjectDegree constraintsen
dc.subjectVertex partitionen
dc.subjectGraphen
dc.subject.ddc511en
dc.titleApproximation of satisfactory bisection problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe Satisfactory Bisection problem means to decide whether a given graph has a partition of its vertex set into two parts of the same cardinality such that each vertex has at least as many neighbors in its part as in the other part. A related variant of this problem, called Co-Satisfactory Bisection, requires that each vertex has at most as many neighbors in its part as in the other part. A vertex satisfying the degree constraint above in a partition is called ‘satisfied’ or ‘co-satisfied,’ respectively. After stating the NP-completeness of both problems, we study approximation results in two directions. We prove that maximizing the number of (co-)satisfied vertices in a bisection has no polynomial-time approximation scheme (unless P=NP), whereas constant approximation algorithms can be obtained in polynomial time. Moreover, minimizing the difference of the cardinalities of vertex classes in a bipartition that (co-)satisfies all vertices has no polynomial-time approximation scheme either.en
dc.relation.isversionofjnlnameJournal of Computer and System Sciences
dc.relation.isversionofjnlvol74en
dc.relation.isversionofjnlissue5en
dc.relation.isversionofjnldate2008-08
dc.relation.isversionofjnlpages875-883en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.jcss.2007.12.001en
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