Thumbnail - No thumbnail

A generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratios

Paschos, Vangelis; Demange, Marc (1997), A generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratios, European Journal of Operational Research, 97, 3, p. 580-592. http://dx.doi.org/10.1016/S0377-2217(96)00271-8

Type
Article accepté pour publication ou publié
External document link
http://www.lamsade.dauphine.fr/FILES/publi166.pdf
Date
1997
Journal name
European Journal of Operational Research
Volume
97
Number
3
Publisher
Elsevier
Pages
580-592
Publication identifier
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Demange, Marc
Abstract (EN)
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.
Subjects / Keywords
Graph theory; Linear programming; Integer programming; Heuristics; Complexity