Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2009-10-05T08:05:49Z
dc.date.available2009-10-05T08:05:49Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2107
dc.language.isoenen
dc.subjectColoringen
dc.subjectGraph algorithmsen
dc.subjectApproximation algorithmsen
dc.subjectCombinatorial optimizationen
dc.subjectk-partite graphsen
dc.subjectWeighted independent seten
dc.subject.ddc003en
dc.titleA simple approximation algorithm for WIS based on the approximability in k-partite graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this note, simple approximation algorithms for the weighted independent set problem are presented with a performance ratio depending on Δ(G). These algorithms do not improve the best approximation algorithm known so far for this problem but they are of interest because of their simplicity. Precisely, we show how an optimum weighted independent set in bipartite graphs and a ρ-approximation of WIS in k-partite graphs respectively allows to obtain a 2/Δ(G)-approximation and a k/Δ(G)ρ -approximation in general graphs. Note that the ratio 2/Δ(G)is the best bound known for the particular cases Δ(G) = 3 or Δ(G) = 4.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol171en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2006
dc.relation.isversionofjnlpages346-348en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2005.01.058en
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