A (2+epsilon)-approximation scheme for minimum domination on circle graphs
DSpace at IIT Bombay
View Archive InfoField | Value | |
Title |
A (2+epsilon)-approximation scheme for minimum domination on circle graphs
|
|
Creator |
DAMIAN-IORDACHE, M
PEMMARAJU, SV |
|
Subject |
approximation algorithms
combinatorial approximation algorithms circle graphs dominating sets |
|
Description |
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(2)) time 8-approximation algorithm for this problem and then extend it to an O(n(3) + 6/epsilonn([6/epsilon+1])m) time (2 + epsilon)-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 + epsilon)-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. .
|
|
Publisher |
ACADEMIC PRESS INC ELSEVIER SCIENCE
|
|
Date |
2011-07-12T13:28:18Z
2011-12-26T12:48:54Z 2011-12-27T05:34:25Z 2011-07-12T13:28:18Z 2011-12-26T12:48:54Z 2011-12-27T05:34:25Z 2002 |
|
Type |
Article
|
|
Identifier |
JOURNAL OF ALGORITHMS, 42(2), 255-276
0196-6774 http://dx.doi.org/10.1006/jagm.2001.1206 http://dspace.library.iitb.ac.in/xmlui/handle/10054/3338 http://hdl.handle.net/10054/3338 |
|
Language |
en
|
|