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

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Improved approximations for weighted and unweighted graph problems

Thumbnail
Date
2005
Dewey
Recherche opérationnelle
Sujet
Minimum chromatic sum; Minimum coloring problem; Maximum clique; Maximum independant set
Journal issue
Theory of Computing Systems
Volume
38
Number
6
Publication date
11-2005
Article pages
763-787
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s00224-004-1162-6
URI
https://basepub.dauphine.fr/handle/123456789/3977
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Demange, Marc
Paschos, Vangelis
Type
Article accepté pour publication ou publié
Abstract (EN)
We obtain improved approximation ratios for problems of a broad class called weighted hereditary induced-subgraph maximization problems, in particular for the maximum independent set, maximum clique and maximum ℓ-colorable induced subgraph, as well as for the minimum coloring problem. We also study the minimum chromatic sum and show that its weighted version polynomially reduces to the weighted independent set problem in such a way that approximation ratios are preserved (up to a multiplicative constant).

  • 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

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.