• 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 maximum independent set via approximation chains

Thumbnail
Date
1997
Dewey
Recherche opérationnelle
Sujet
Independent set; Approximation algorithm; Complexity; NP-complete problem; Graph
Journal issue
Applied Mathematics Letters
Volume
10
Number
3
Publication date
1997
Article pages
105-110
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/S0893-9659(97)00044-X
URI
https://basepub.dauphine.fr/handle/123456789/2950
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Demange, Marc
Paschos, Vangelis
Type
Article accepté pour publication ou publié
Abstract (EN)
We first define the notion of approximation chain and then we use it to obtain, in polynomial time, asymptotic approximation ratio of min{κ/μ, [κ′ log(logΔ)]/Δ} (where κ is a fixed positive constant, κ′ is a constant depending on κ, and Δ, μ are the maximum and the average degrees of the graph, respectively). This result essentially improves, from both complexity and approximation quality points of view, the best-known approximation ratio for maximum independent set.

  • 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.