@inproceedings{8689059e3f3048f794a5978254e5f89f,
title = "A d/2 approximation for maximum weight independent set in d-claw free graphs",
abstract = "In this paper we consider the following problem. Given is a d-claw free graph G = (V; E;w) where w: V → R+. Our algorithm finds an independent set A such that w(A *)/w(A) ≤ d/2 where A * is an independent that maximizes w(A *). The previous best polynomial time approximation algorithm obtained w(A *)/w(A) ≤ 2d/3.",
author = "Piotr Berman",
year = "2000",
month = jan,
day = "1",
doi = "10.1007/3-540-44985-X",
language = "English (US)",
isbn = "3540676902",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "214--219",
editor = "Halld{\'o}rsson, {Magn{\'u}s M.}",
booktitle = "Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings",
address = "Germany",
note = "7th Scandinavian Workshop on Algorithm Theory, SWAT 2000 ; Conference date: 05-07-2000 Through 07-07-2000",
}