| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428456 | Information Processing Letters | 2006 | 7 Pages |
Abstract
We show that the problem of finding a minimum dominating set in a circle graph is APX-hard: there is a constant δ>0 such that there is no (1+δ)-approximation algorithm for the minimum dominating set problem on circle graphs unless P=NP. Hence a PTAS for this problem seems unlikely. This hardness result complements the (2+ɛ)-approximation algorithm for the problem [M. Damian, S.V. Pemmaraju, A (2+ɛ)-approximation scheme for minimum domination on circle graphs, J. Algorithms 42 (2) (2002) 255–276].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
