Show simple item record

dc.contributor.authorDemange, Marc
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorde Werra, Dominique
dc.date.accessioned2009-11-20T09:32:23Z
dc.date.available2009-11-20T09:32:23Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2480
dc.language.isoenen
dc.subjectApproximabilityen
dc.subjectBatch schedulingen
dc.subjectGraph coloringen
dc.subject.ddc003en
dc.titleA hypocoloring model for batch schedulingen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherESSEC;France
dc.contributor.editoruniversityotherEcole Polytechnique Fédérale de Lausanne,;Suisse
dc.description.abstractenStarting from a batch scheduling problem, we consider a weighted subcoloring in a graph G; each node v has a weight w(v); each color class S is a subset of nodes which generates a collection of node disjoint cliques. The weight w(S) is defined as View the MathML source. In the scheduling problem, the completion time is given by View the MathML source where S=(S1,…,Sk) is a partition of the node set of graph G into color classes as defined above. Properties of such colorings concerning special classes of graphs (line graphs of cacti, block graphs) are stated; complexity and approximability results are presented. The associated decision problem is shown to be NP-complete for bipartite graphs with maximum degree at most 39 and triangle-free planar graphs with maximum degree k for any kgreater-or-equal, slanted3. Polynomial algorithms are given for graphs with maximum degree two and for the forests with maximum degree k. An (exponential) algorithm based on a simple separation principle is sketched for graphs without triangles.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol146en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2005-02
dc.relation.isversionofjnlpages3-26en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2004.06.016en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record