Better approximation schemes for disk graphs

E.J. Leeuwen, van

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    15 Citations (Scopus)

    Abstract

    We consider Maximum Independent Set and Minimum Vertex Cover on disk graphs. We propose an asymptotic FPTAS for Minimum Vertex Cover on disk graphs of bounded ply. This scheme can be extended to an EPTAS on arbitrary disk graphs, improving on the previously known PTAS [8]. We introduce the notion of level density for disk graphs, which is a generalization of the notion of ply. We give an asymptotic FPTAS for Maximum Independent Set on disk graphs of bounded level density, which is also a PTAS on arbitrary disk graphs. The schemes are a geometric generalization of Baker’s EPTASs for planar graphs [3].
    Original languageEnglish
    Title of host publicationAlgorithm Theory - SWAT 2006 : 10th Scandinavian Workshop, Riga, Latvia, July 6-8, 2006 : proceedings
    EditorsL. Arge, R. Freivalds
    Place of PublicationBerlin
    PublisherSpringer
    Pages316-327
    ISBN (Print)3-540-35753-X
    DOIs
    Publication statusPublished - 2006

    Publication series

    NameLecture Notes in Computer Science
    Volume4059
    ISSN (Print)0302-9743

    Fingerprint Dive into the research topics of 'Better approximation schemes for disk graphs'. Together they form a unique fingerprint.

    Cite this