Show simple item record

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


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