• 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 - Request a copy

Improved approximations for maximum independent set via approximation chains

Demange, Marc; Paschos, Vangelis (1997), Improved approximations for maximum independent set via approximation chains, Applied Mathematics Letters, 10, 3, p. 105-110. http://dx.doi.org/10.1016/S0893-9659(97)00044-X

Type
Article accepté pour publication ou publié
Date
1997
Journal name
Applied Mathematics Letters
Volume
10
Number
3
Publisher
Elsevier
Pages
105-110
Publication identifier
http://dx.doi.org/10.1016/S0893-9659(97)00044-X
Metadata
Show full item record
Author(s)
Demange, Marc
Paschos, Vangelis
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.
Subjects / Keywords
Independent set; Approximation algorithm; Complexity; NP-complete problem; Graph

Related items

Showing items related by title and author.

  • Thumbnail
    A generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratios 
    Paschos, Vangelis; Demange, Marc (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
    Maximum independent set and linear programming 
    Demange, Marc; Paschos, Vangelis (1995) 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
    Maximum-weight independent set is as "well" approximated as the unweighted one 
    Demange, Marc; Paschos, Vangelis (1999) Document de travail / Working paper
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