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
1997Journal name
Applied Mathematics LettersVolume
10Number
3Publisher
Elsevier
Pages
105-110
Publication identifier
Metadata
Show full item recordAbstract (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; GraphRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Demange, Marc (1997) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (1996) Communication / Conférence
-
Demange, Marc; Paschos, Vangelis (1995) Communication / Conférence
-
Demange, Marc; Paschos, Vangelis (1997) Article accepté pour publication ou publié
-
Demange, Marc; Paschos, Vangelis (1999) Document de travail / Working paper