Show simple item record

dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-01-14T15:38:01Z
dc.date.available2010-01-14T15:38:01Z
dc.date.issued1997
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2950
dc.language.isoenen
dc.subjectIndependent seten
dc.subjectApproximation algorithmen
dc.subjectComplexityen
dc.subjectNP-complete problemen
dc.subjectGraphen
dc.subject.ddc003en
dc.titleImproved approximations for maximum independent set via approximation chainsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherCERMSEM, Université Paris I;France
dc.description.abstractenWe first define the notion of approximation chain and then we use it to obtain, in polynomial time, asymptotic approximation ratio of min{κ/μ, [κ′ log(logΔ)]/Δ} (where κ is a fixed positive constant, κ′ is a constant depending on κ, and Δ, μ are the maximum and the average degrees of the graph, respectively). This result essentially improves, from both complexity and approximation quality points of view, the best-known approximation ratio for maximum independent set.en
dc.relation.isversionofjnlnameApplied Mathematics Letters
dc.relation.isversionofjnlvol10en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate1997
dc.relation.isversionofjnlpages105-110en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0893-9659(97)00044-Xen
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
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