• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
http://dx.doi.org/10.1016/S0377-2217(96)00271-8
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

Related items

Showing items related by title and author.

  • Thumbnail
    Improved approximations for maximum independent set via approximation chains 
    Demange, Marc; Paschos, Vangelis (1997) Article accepté pour publication ou publié
  • Thumbnail
    Constructive-non-constructive approximation and maximum independent set problem 
    Demange, Marc; Paschos, Vangelis (1996) Communication / Conférence
  • Thumbnail
    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é
  • Thumbnail
    Improved approximations for weighted and unweighted graph problems 
    Demange, Marc; Paschos, Vangelis (2005) Article accepté pour publication ou publié
  • Thumbnail
    A note on the improvement of the maximum independent set's approximation ratio 
    Paschos, Vangelis (1995) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo