Show simple item record

dc.contributor.authorRies, Bernard*
dc.contributor.authorPop, Petrica*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorDemange, Marc*
dc.date.accessioned2013-05-07T10:05:20Z
dc.date.available2013-05-07T10:05:20Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11279
dc.language.isoenen
dc.subjectClusteringen
dc.subjectComplete qq-partite graphsen
dc.subjectSplit graphsen
dc.subjectBipartite graphsen
dc.subjectSchedulingen
dc.subjectPTASen
dc.subjectApproximation algorithmsen
dc.subjectComputational complexityen
dc.subject.ddc511en
dc.titleOn the complexity of the selective graph coloring problem in some special classes of graphsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherTechnical University of Cluj-Napoca, North University Center of Baia Mare;Roumanie
dc.description.abstractenIn this paper, we consider the selective graph coloring problem. Given an integer k≥1k≥1 and a graph G=(V,E)G=(V,E) with a partition V1,…,VpV1,…,Vp of VV, it consists in deciding whether there exists a set V∗V∗ in GG such that ∣V∗∩Vi∣=1∣V∗∩Vi∣=1 for all i∈{1,…,p}i∈{1,…,p}, and such that the graph induced by V∗V∗ is kk-colorable. We investigate the complexity status of this problem in various classes of graphs.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol540-541
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages89-102
dc.relation.isversionofdoi10.1016/j.tcs.2013.04.018en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds989*
hal.person.labIds40626*
hal.person.labIds989*
hal.person.labIds24359*
hal.identifierhal-01508790*


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