Afficher la notice abrégée

dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-04-16T08:16:14Z
dc.date.available2010-04-16T08:16:14Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3977
dc.language.isoenen
dc.subjectMinimum chromatic sumen
dc.subjectMinimum coloring problemen
dc.subjectMaximum cliqueen
dc.subjectMaximum independant seten
dc.subject.ddc003en
dc.titleImproved approximations for weighted and unweighted graph problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe obtain improved approximation ratios for problems of a broad class called weighted hereditary induced-subgraph maximization problems, in particular for the maximum independent set, maximum clique and maximum ℓ-colorable induced subgraph, as well as for the minimum coloring problem. We also study the minimum chromatic sum and show that its weighted version polynomially reduces to the weighted independent set problem in such a way that approximation ratios are preserved (up to a multiplicative constant).en
dc.relation.isversionofjnlnameTheory of Computing Systems
dc.relation.isversionofjnlvol38en
dc.relation.isversionofjnlissue6en
dc.relation.isversionofjnldate2005-11
dc.relation.isversionofjnlpages763-787en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s00224-004-1162-6en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Fichiers attachés à cette notice

FichiersTailleFormatConsulter

Il n'y a pas de fichiers associés à cette notice.

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

Afficher la notice abrégée