Book chapter
Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs
Algorithms and Computation, pp.70-82
Lecture Notes in Computer Science, Springer Berlin Heidelberg
03/03/2000
DOI: 10.1007/3-540-46632-0_8
Abstract
A graph G = (V,E) is called a circle graph if there is a one- to-one correspondence between vertices in V and a set C of chords in a circle such that two vertices in V are adjacent if and only if the corre- sponding chords in C intersect. A subset V′ of V is a dominating set of G if for all u ∈ V either u ∈ V′ or u has a neighbor in V′. In addition, if G[V′] is connected, then V′ is called a connected dominating set; if G[V′] has no isolated vertices, then V′ is called a total dominating set. Keil (Discrete Applied Mathematics, 42 (1993), 51–63) shows that the minimum dominating set problem (MDS), the minimum connected dominating set problem (MCDS) and the minimum total domination problem (MTDS) are all NP-complete even for circle graphs. He mentions designing approximation algorithms for these problems as being open. This paper presents O(1)-approximation algorithms for all three problems — MDS, MCDS, and MTDS on circle graphs. For any circle graph with n vertices and m edges, these algorithms take O(n2 + nm) time and O(n2) space. These results, along with the result on the hardness of approximating minimum independent dominating set on circle graphs (Damian-Iordache and Pemmaraju, in this proceedings) advance our understanding of domination problems on circle graphs significantly.
Details
- Title: Subtitle
- Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs
- Creators
- Mirela Damian-Iordache - University of IowaSriram V. Pemmaraju - Indian Institute of Technology Indore
- Resource Type
- Book chapter
- Publication Details
- Algorithms and Computation, pp.70-82
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/3-540-46632-0_8
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 03/03/2000
- Academic Unit
- Computer Science
- Record Identifier
- 9984259493102771
Metrics
4 Record Views