Journal article
APX-hardness of domination problems in circle graphs
Information processing letters, Vol.97(6), pp.231-237
2006
DOI: 10.1016/j.ipl.2005.11.007
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].
Details
- Title: Subtitle
- APX-hardness of domination problems in circle graphs
- Creators
- Mirela Damian - Villanova UniversitySriram V Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Information processing letters, Vol.97(6), pp.231-237
- Publisher
- Elsevier B.V
- DOI
- 10.1016/j.ipl.2005.11.007
- ISSN
- 0020-0190
- eISSN
- 1872-6119
- Language
- English
- Date published
- 2006
- Academic Unit
- Computer Science
- Record Identifier
- 9984259436602771
Metrics
15 Record Views