## Abstract

We present local 1∈+∈ε approximation algorithms for the minimum dominating and the connected dominating set problems in location aware Unit Disk Graphs (UDGs). Our algorithms are local in the sense that the status of a vertex v in the output (i.e. whether or not v is part of the set to be computed) depends only on the vertices which are a constant number of edges (hops) away from v. This constant is independent of the size of the network. In our graph model we assume that each vertex knows its geographic coordinates in the plane (location aware nodes). Our algorithms give the best approximation ratios known for this setting. Moreover, the processing time that each vertex needs to determine whether or not it is part of the computed set is bounded by a polynomial in the number of vertices which are a constant number of hops away from it. We employ a new method for constructing the connected dominating set and we give the first analysis of trade-offs between approximation ratio and locality distance.

Original language | English |
---|---|

Pages (from-to) | 227-240 |

Number of pages | 14 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 5426 LNCS |

DOIs | |

State | Published - 2009 |

Externally published | Yes |

Event | 6th International Workshop on Approximation and Online Algorithms, WAOA 2008 - Karlsruhe, Germany Duration: 18 Sep 2008 → 19 Sep 2008 |