Approximating maximum independent set in bounded degree graphs

Piotr Berman, Martin Furer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

69 Scopus citations

Abstract

For every Δ>2 and ε>0 we present a polynomial time approximation algorithm for the Maximum Independent Set problem, that in a graph of degree Δ approximates an optimal solution within ratio 5/Δ+3-ε for even Δ and within ratio 5/Δ+3.25-ε for odd Δ.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages365-371
Number of pages7
ISBN (Print)0898713293
StatePublished - 1994
EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
Duration: Jan 23 1994Jan 25 1994

Publication series

NameProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

Other

OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
CityArlington, VA, USA
Period1/23/941/25/94

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Approximating maximum independent set in bounded degree graphs'. Together they form a unique fingerprint.

Cite this