Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorDemange, Marc
dc.date.accessioned2009-12-11T08:42:04Z
dc.date.available2009-12-11T08:42:04Z
dc.date.issued1997
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2664
dc.language.isoenen
dc.subjectGraph theoryen
dc.subjectLinear programmingen
dc.subjectInteger programmingen
dc.subjectHeuristicsen
dc.subjectComplexityen
dc.subject.ddc003en
dc.titleA generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratiosen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe first study a generalization of the König-Egervary graphs, the class of the κ-KE graphs, and propose an exact polynomial time algorithm solving maximum independent set problem in this class. Next, we show how this result can be efficiently used to devise polynomial time approximation algorithms with improved approximation ratios for the maximum independent set problem in general graphs.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol97en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate1997-03
dc.relation.isversionofjnlpages580-592en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0377-2217(96)00271-8en
dc.identifier.urlsitehttp://www.lamsade.dauphine.fr/FILES/publi166.pdfen
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