### Abstract

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

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 7 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2003 |

### Publication series

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

Publisher | University of Twente, Department of Applied Mathematics |

No. | 1688 |

ISSN (Print) | 0169-2690 |

### Keywords

- MSC-05C62
- IR-65873
- METIS-213742
- MSC-05C69
- EWI-3508
- MSC-68R10
- MSC-90C35

### Cite this

*A new PTAS for maximum independent sets in unit disk graphs*. (Memorandum Afdeling TW; No. 1688). Enschede: University of Twente, Department of Applied Mathematics.

}

*A new PTAS for maximum independent sets in unit disk graphs*. Memorandum Afdeling TW, no. 1688, University of Twente, Department of Applied Mathematics, Enschede.

**A new PTAS for maximum independent sets in unit disk graphs.** / Nieberg, T.; Hurink, Johann L.; Kern, Walter.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - A new PTAS for maximum independent sets in unit disk graphs

AU - Nieberg, T.

AU - Hurink, Johann L.

AU - Kern, Walter

N1 - Imported from MEMORANDA

PY - 2003

Y1 - 2003

N2 - A unit disk graph is an intersection graph of unit disks in the euclidean plane. We present a polynomial-time approximation scheme for the maximum independent set problem in unit disk graphs. In contrast to previously known approximation schemes, our approach does not require a geometric representation (specifying the coordinates of the disk centers).

AB - A unit disk graph is an intersection graph of unit disks in the euclidean plane. We present a polynomial-time approximation scheme for the maximum independent set problem in unit disk graphs. In contrast to previously known approximation schemes, our approach does not require a geometric representation (specifying the coordinates of the disk centers).

KW - MSC-05C62

KW - IR-65873

KW - METIS-213742

KW - MSC-05C69

KW - EWI-3508

KW - MSC-68R10

KW - MSC-90C35

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

BT - A new PTAS for maximum independent sets in unit disk graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -