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

Piotr Berman

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

    69 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 languageEnglish (US)
    Title of host publicationAlgorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings
    EditorsMagnús M. Halldórsson
    PublisherSpringer Verlag
    Pages214-219
    Number of pages6
    ISBN (Print)3540676902, 9783540676904
    DOIs
    StatePublished - Jan 1 2000
    Event7th Scandinavian Workshop on Algorithm Theory, SWAT 2000 - Bergen, Norway
    Duration: Jul 5 2000Jul 7 2000

    Publication series

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

    Other

    Other7th Scandinavian Workshop on Algorithm Theory, SWAT 2000
    Country/TerritoryNorway
    CityBergen
    Period7/5/007/7/00

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'A d/2 approximation for maximum weight independent set in d-claw free graphs'. Together they form a unique fingerprint.

    Cite this