Approximation algorithms for unit disk graphs

E.J. Leeuwen, van

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

    26 Citations (Scopus)


    We consider several graph theoretic problems on unit disk graphs (Maximum Independent Set, Minimum Vertex Cover, and Minimum (Connected) Dominating Set) relevant to mobile ad hoc networks. We propose two new notions: thickness and density. If the thickness of a unit disk graph is bounded, then the mentioned problems can be solved in polynomial time. For unit disk graphs of bounded density, we present a new asymptotic fully-polynomial approximation scheme for the considered problems. The scheme for Minimum Connected Dominating Set is the first Baker-like asymptotic FPTAS for this problem. By adapting the proof, it implies e.g. an asymptotic FPTAS for Minimum Connected Dominating Set on planar graphs.
    Original languageEnglish
    Title of host publicationGraph-Theoretic Concepts in Computer Science
    Subtitle of host publication31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers
    EditorsD. Kratsch
    Place of PublicationBerlin
    Number of pages11
    ISBN (Electronic)978-3-540-31468-4
    ISBN (Print)3-540-31000-2, 978-3-540-31000-6
    Publication statusPublished - 2005

    Publication series

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


    Dive into the research topics of 'Approximation algorithms for unit disk graphs'. Together they form a unique fingerprint.

    Cite this