A (°/2)-approximation algorithm for the maximum independent set problem

Paschos, Vangelis

Paschos, Vangelis (1992), A (°/2)-approximation algorithm for the maximum independent set problem, Information Processing Letters, 44, 1, p. 11-13. http://dx.doi.org/10.1016/0020-0190(92)90248-T

Type

Article accepté pour publication ou publié

Date

1992

Journal name

Information Processing Letters

Volume

Number

Publisher

Elsevier

Pages

11-13

Abstract (EN)

We show how we can improve the approximation ratio for the independent set problem on a graph. We obtain thus an approximation ratio asymptotically equal to δ/2, in place of δ−1, where δ is the maximum degree of the graph.

Subjects / Keywords

computational complexity; independent set; combinatorial problems; analysis of algorithms; Approximation algorithms