• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

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

Thumbnail
Date
1997
Lien vers un document non conservé dans cette base
http://www.lamsade.dauphine.fr/FILES/publi166.pdf
Indexation documentaire
Recherche opérationnelle
Subject
Graph theory; Linear programming; Integer programming; Heuristics; Complexity
Nom de la revue
European Journal of Operational Research
Volume
97
Numéro
3
Date de publication
03-1997
Pages article
580-592
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/S0377-2217(96)00271-8
URI
https://basepub.dauphine.fr/handle/123456789/2664
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Paschos, Vangelis
Demange, Marc
Type
Article accepté pour publication ou publié
Résumé en anglais
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.