### Abstract

We present a polynomial-time approximation scheme (PTAS) for the minimum dominating set problem in unit disk graphs. In contrast to previously known approximation schemes for the minimum dominating set problem on unit disk graphs, our approach does not assume a geometric representation of the vertices (specifying the positions of the disks in the plane) to be given as part of the input.

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 14 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2004 |

### Publication series

Name | Memorandum Afdeling TW |
---|---|

Publisher | University of Twente, Department of Applied Mathematics |

No. | 1732 |

ISSN (Print) | 0169-2690 |

### Keywords

- METIS-219688
- MSC-05R69
- EWI-3552
- EC Grant Agreement nr.: FP5/34734
- IR-65916
- MSC-05R62
- MSC-68R10

## Cite this

Nieberg, T., & Hurink, J. L. (2004).

*A PTAS for the minimum dominating set problem in unit disk graphs*. (Memorandum Afdeling TW; No. 1732). Enschede: University of Twente, Department of Applied Mathematics.