A GENERALIZATION OF KONIG-EGERVARY GRAPHS AND HEURISTICS FOR THE MAXIMUM INDEPENDENT SET PROBLEM WITH IMPROVED APPROXIMATION RATIOS

Authors
PASCHOS VT DEMANGE M
Citation
Vt. Paschos et M. Demange, A GENERALIZATION OF KONIG-EGERVARY GRAPHS AND HEURISTICS FOR THE MAXIMUM INDEPENDENT SET PROBLEM WITH IMPROVED APPROXIMATION RATIOS, European journal of operational research, 97(3), 1997, pp. 580-592
Citations number
10
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
97
Issue
3
Year of publication
1997
Pages
580 - 592
Database
ISI
SICI code
0377-2217(1997)97:3<580:AGOKGA>2.0.ZU;2-V
Abstract
We first study a generalization of the Konig-Egervary graphs, the clas s of the kappa-KE graphs, and propose an exact polynomial time algorit hm solving maximum independent set problem in this class. Next, we sho w how this result can be efficiently used to devise polynomial time ap proximation algorithms with improved approximation ratios for the maxi mum independent set problem in general graphs. (C) 1997 Elsevier Scien ce B.V.