| Article ID: | iaor19991395 |
| Country: | Netherlands |
| Volume: | 97 |
| Issue: | 3 |
| Start Page Number: | 580 |
| End Page Number: | 592 |
| Publication Date: | Mar 1997 |
| Journal: | European Journal of Operational Research |
| Authors: | Paschos Vangelis Th., Demange Marc |
| Keywords: | heuristics, sets |
We 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.