@inproceedings{ef5b9596812a4626a131a35b8184e4a5,

title = "Approximating maximum independent set in bounded degree graphs",

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 Δ.",

author = "Piotr Berman and Martin Furer",

year = "1994",

language = "English (US)",

isbn = "0898713293",

series = "Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms",

publisher = "Publ by ACM",

pages = "365--371",

booktitle = "Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms",

note = "Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-1994 Through 25-01-1994",

}