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.pdfDate
1997Journal name
European Journal of Operational ResearchVolume
97Number
3Publisher
Elsevier
Pages
580-592
Publication identifier
Metadata
Show full item recordAbstract (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; ComplexityRelated items
Showing items related by title and author.
-
Demange, Marc; Paschos, Vangelis (1997) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (1996) Communication / Conférence
-
Demange, Marc; Paschos, Vangelis (1997) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (2005) Article accepté pour publication ou publié
-
Paschos, Vangelis (1995) Article accepté pour publication ou publié