Local PTAS for independent set and vertex cover in location aware unit disk graphs

Andreas Wiese, Evangelos Kranakis

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We present the first local approximation schemes for maximum independent set and minimum vertex cover in unit disk graphs. In the graph model we assume that each node knows its geographic coordinates in the plane. Our algorithms are local in the sense that the status of each node v (whether or not v is in the computed set) depends only on the vertices which are a constant number of hops away from v. This constant is independent of the size of the network.We give upper bounds for the constant depending on the desired approximation ratio. Our algorithms give the best possible approximation ratios for this setting. The technique which we use to obtain the algorithm for vertex cover can also be employed for constructing the first global PTAS for this problem in unit disk graph which does not need the embedding of the graph as part of the input.

Original languageEnglish
Pages (from-to)273-293
Number of pages21
JournalAd-Hoc and Sensor Wireless Networks
Volume7
Issue number3-4
StatePublished - 2009
Externally publishedYes

Keywords

  • Approximation schemes
  • Independent set
  • Local algorithms
  • Location aware nodes
  • Unit disk graphs
  • Vertex cover

Fingerprint

Dive into the research topics of 'Local PTAS for independent set and vertex cover in location aware unit disk graphs'. Together they form a unique fingerprint.

Cite this