A (°/2)-approximation algorithm for the maximum independent set problem

dc.contributor.author	Paschos, Vangelis
dc.date.accessioned	2010-04-27T07:45:47Z
dc.date.available	2010-04-27T07:45:47Z
dc.date.issued	1992
dc.identifier.uri	https://basepub.dauphine.fr/handle/123456789/4004
dc.language.iso	en	en
dc.subject	computational complexity	en
dc.subject	independent set	en
dc.subject	combinatorial problems	en
dc.subject	analysis of algorithms	en
dc.subject	Approximation algorithms	en
dc.subject.ddc	003	en
dc.title	A (°/2)-approximation algorithm for the maximum independent set problem	en
dc.type	Article accepté pour publication ou publié
dc.description.abstracten	We show how we can improve the approximation ratio for the independent set problem on a graph. We obtain thus an approximation ratio asymptotically equal to δ/2, in place of δ−1, where δ is the maximum degree of the graph.	en
dc.relation.isversionofjnlname	Information Processing Letters
dc.relation.isversionofjnlvol	44	en
dc.relation.isversionofjnlissue	1	en
dc.relation.isversionofjnldate	1992-11
dc.relation.isversionofjnlpages	11-13	en
dc.relation.isversionofdoi	http://dx.doi.org/10.1016/0020-0190(92)90248-T	en
dc.description.sponsorshipprivate	oui	en
dc.relation.isversionofjnlpublisher	Elsevier	en
dc.subject.ddclabel	Recherche opérationnelle	en

Files in this item

Files	Size	Format	View
There are no files associated with this item.