Conference proceeding
(2+ epsilon )-approximation scheme for minimum domination on circle graphs
SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pp.672-679
02/2000
Abstract
The main result of this paper is a (2+ epsilon )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n super(2)) time 8-approximation algorithm for the minimum dominating set problem on circle graphs and then extend it to a (2+ epsilon )-approximation scheme that solves the minimum dominating set problem in time O(n super(3)+6/ epsilon n super(6/ epsilon +1)m). 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+ epsilon )-approximation schemes for the minimum connected dominating set and the minimum total dominating set problems on circle graphs. Keil showed that these problems are NP-complete for circle graphs and left open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs and involve techniques that may lead to new approximation algorithms for other problems like vertex cover and chromatic number on circle graphs.
Details
- Title: Subtitle
- (2+ epsilon )-approximation scheme for minimum domination on circle graphs
- Creators
- Mirela Damian-IordacheSriram Pemmaraju
- Resource Type
- Conference proceeding
- Publication Details
- SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pp.672-679
- Language
- English
- Date published
- 02/2000
- Academic Unit
- Computer Science
- Record Identifier
- 9984411070902771
Metrics
6 Record Views