Journal article
A (2 + ε)-Approximation Scheme for Minimum Domination on Circle Graphs
Journal of algorithms, Vol.42(2), pp.255-276
02/2002
DOI: 10.1006/jagm.2001.1206
Abstract
The main result of this paper is a (2+ε)-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n2) time 8-approximation algorithm for this problem and then extend it to an O(n3+6εn⌈+1⌉m) time (2+ε)-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3+ε)-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.
Details
- Title: Subtitle
- A (2 + ε)-Approximation Scheme for Minimum Domination on Circle Graphs
- Creators
- Mirela Damian-Iordache - Ursinus CollegeSriram V Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Journal of algorithms, Vol.42(2), pp.255-276
- Publisher
- Elsevier Inc
- DOI
- 10.1006/jagm.2001.1206
- ISSN
- 0196-6774
- eISSN
- 1090-2678
- Language
- English
- Date published
- 02/2002
- Academic Unit
- Computer Science
- Record Identifier
- 9984259499302771
Metrics
4 Record Views