Improved approximations for maximum independent set via approximation chains

Demange, Marc; Paschos, Vangelis

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

Number

Publisher

Elsevier

Pages

105-110

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