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
TypeArticle accepté pour publication ou publié
External document linkhttp://www.lamsade.dauphine.fr/FILES/publi166.pdf
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
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 / KeywordsGraph theory; Linear programming; Integer programming; Heuristics; Complexity
Showing items related by title and author.
The approximability behavior of some combinatorial problems with respect to the approximability of a class of maximum independent set problems Demange, Marc; Paschos, Vangelis (1997) Article accepté pour publication ou publié