Show simple item record

dc.contributor.authorBourgeois, Nicolas
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-12-10T09:35:25Z
dc.date.available2009-12-10T09:35:25Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2649
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectExponential algorithmsen
dc.subjectMin coloring problemen
dc.subject.ddc003en
dc.titleApproximation of MIN COLORING by moderately exponential algorithmsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study in this note approximation algorithms for the problem of coloring the vertices of a graph with as few colors as possible, with moderately exponential running times (and using either polynomial or exponential space), better than those of exact computation. Study of approximation is performed with respect to optimality measures, the minimum number of used colors and the maximum number of unused colors.en
dc.relation.isversionofjnlnameInformation Processing Letters
dc.relation.isversionofjnlvol109en
dc.relation.isversionofjnlissue16en
dc.relation.isversionofjnldate2009-07
dc.relation.isversionofjnlpages950-954en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ipl.2009.05.002en
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