A d/2 approximation for maximum weight independent set in d-claw free graphs

Piotr Berman

doi:10.1007/3-540-44985-X

A d/2 approximation for maximum weight independent set in d-claw free graphs

Piotr Berman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

64 Scopus citations

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.

Original language	English (US)
Title of host publication	Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings
Editors	Magnús M. Halldórsson
Publisher	Springer Verlag
Pages	214-219
Number of pages	6
ISBN (Print)	3540676902, 9783540676904
DOIs	https://doi.org/10.1007/3-540-44985-X
State	Published - Jan 1 2000
Event	7th Scandinavian Workshop on Algorithm Theory, SWAT 2000 - Bergen, Norway Duration: Jul 5 2000 → Jul 7 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1851
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th Scandinavian Workshop on Algorithm Theory, SWAT 2000
Country/Territory	Norway
City	Bergen
Period	7/5/00 → 7/7/00

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-44985-X

Cite this

Berman, P. (2000). A d/2 approximation for maximum weight independent set in d-claw free graphs. In M. M. Halldórsson (Ed.), Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings (pp. 214-219). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1851). Springer Verlag. https://doi.org/10.1007/3-540-44985-X

Berman, Piotr. / A d/2 approximation for maximum weight independent set in d-claw free graphs. Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. editor / Magnús M. Halldórsson. Springer Verlag, 2000. pp. 214-219 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

}

Berman, P 2000, A d/2 approximation for maximum weight independent set in d-claw free graphs. in MM Halldórsson (ed.), Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1851, Springer Verlag, pp. 214-219, 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000, Bergen, Norway, 7/5/00. https://doi.org/10.1007/3-540-44985-X

A d/2 approximation for maximum weight independent set in d-claw free graphs. / Berman, Piotr.
Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. ed. / Magnús M. Halldórsson. Springer Verlag, 2000. p. 214-219 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1851).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A d/2 approximation for maximum weight independent set in d-claw free graphs

AU - Berman, Piotr

PY - 2000/1/1

Y1 - 2000/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84956867923&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84956867923&partnerID=8YFLogxK

U2 - 10.1007/3-540-44985-X

DO - 10.1007/3-540-44985-X

M3 - Conference contribution

AN - SCOPUS:84956867923

SN - 3540676902

SN - 9783540676904

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 214

EP - 219

BT - Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings

A2 - Halldórsson, Magnús M.

PB - Springer Verlag

T2 - 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000

Y2 - 5 July 2000 through 7 July 2000

ER -

Berman P. A d/2 approximation for maximum weight independent set in d-claw free graphs. In Halldórsson MM, editor, Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Springer Verlag. 2000. p. 214-219. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44985-X

A d/2 approximation for maximum weight independent set in d-claw free graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this