Afficher la notice abrégée

dc.contributor.authorEscoffier, Bruno
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-04-04T13:41:20Z
dc.date.available2011-04-04T13:41:20Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5888
dc.language.isoenen
dc.subjectApproximation algorithmen
dc.subjectNP-complete problemsen
dc.subjectweighted coloringen
dc.subjectinterval graphsen
dc.subjectline graph of bipartite graphsen
dc.subjectpartial k-treeen
dc.subject.ddc003en
dc.titleWeighted coloring: further complexity and approximability resultsen
dc.typeCommunication / Conférence
dc.description.abstractenGiven a vertex-weighted graph G = (V,E;w), w(v) ≥ 0 for any v ∈ V, we consider a weighted version of the coloring problem which consists in finding a partition S=(S1...,Sk)=(S1Sk) of the vertex set V of G into stable sets and minimizing ∑ i = 1 k w(S i ) where the weight of S is defined as max{w(v) : v ∈ S}. In this paper, we keep on with the investigation of the complexity and the approximability of this problem by mainly answering one of the questions raised by D. J. Guan and X. Zhu (”A Coloring Problem for Weighted Graphs”, Inf. Process. Lett. 61(2):77-81 1997).en
dc.identifier.citationpages205-214en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber3701
dc.relation.ispartoftitleTheoretical Computer Science 9th Italian Conference, ICTCS 2005, Siena, Italy, October 12-14, 2005, Proceedingsen
dc.relation.ispartofeditorPinna, G. Michele
dc.relation.ispartofeditorLodi, Elena
dc.relation.ispartofeditorCoppo, Mario
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2005
dc.relation.ispartofpages411en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/11560586en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-29106-0en
dc.relation.conftitle9th Italian Conference on Theoretical Computer Science (ICTCS'05)en
dc.relation.confdate2005-10
dc.relation.confcitySienneen
dc.relation.confcountryItalieen
dc.identifier.doihttp://dx.doi.org/10.1007/11560586_17


Fichiers attachés à cette notice

Thumbnail

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée