A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs.
The main result of this paper is a (2 + e)approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n 2) time 8approximation algorithm for the minimum dominating set problem on circle graphs and then extend it to a (2+e)approximation scheme that solves the minimum dominating set problem in time O(n 3 + 6g_,f~i +l,~,~ ]. 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 + ~) approximation schemes for the minimum connected dominating set and the minimum total dominating set problems on circle graphs. Keil (Discrete Applied Mathematics, 42 (1993), 5163) showed that these problems are NPcomplete 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.
Main Author:  DamianIordache, Mirela. 

Other Authors:  Pemmaraju, Sriram V. 
Language:  English 
Published: 
2002

Online Access: 
http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175632 
PID 
vudl:175632 

id 
vudl:175632 
modeltype_str_mv 
vudlsystem:CoreModel vudlsystem:CollectionModel vudlsystem:ResourceCollection 
datastream_str_mv 
DC PARENTQUERY PARENTLISTRAW PARENTLIST MEMBERQUERY MEMBERLISTRAW LEGACYMETS LICENSE AGENTS PROCESSMD THUMBNAIL STRUCTMAP RELSEXT 
hierarchytype 

sequence_vudl_175631_str 
0000000001 
has_order_str 
no 
hierarchy_top_id 
vudl:171664 
hierarchy_top_title 
Villanova Digital Collection 
hierarchy_parent_id 
vudl:175631 
hierarchy_parent_title 
Damian Mirela 
hierarchy_sequence 
0000000001 
hierarchy_first_parent_id_str 
vudl:175632 
hierarchy_sequence_sort_str 
0000000001 
hierarchy_all_parents_str_mv 
vudl:171664 vudl:172968 vudl:175631 
first_indexed 
20140111T23:30:12Z 
last_indexed 
20140111T23:30:12Z 
recordtype 
vudl 
fullrecord 
<root>
<url>
http://digital.library.villanova.edu/files/vudl:175632/DC
</url>
<thumbnail>
http://digital.library.villanova.edu/files/vudl:175632/THUMBNAIL
</thumbnail>
</root>

spelling 

institution 
Villanova University 
collection 
Digital Library 
language 
English 
dc_source_str_mv 
Journal of Algorithms 42(2), February 2002, 255276. 
author 
DamianIordache, Mirela. 
author_facet_str_mv 
DamianIordache, Mirela. Pemmaraju, Sriram V. 
author_or_contributor_facet_str_mv 
DamianIordache, Mirela. Pemmaraju, Sriram V. 
author_s 
DamianIordache, Mirela. 
spellingShingle 
DamianIordache, Mirela. A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
authorletter 
DamianIordache, Mirela. 
author_sort_str 
DamianIordache, Mirela. 
author2 
Pemmaraju, Sriram V. 
author2Str 
Pemmaraju, Sriram V. 
dc_title_str 
A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
title 
A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
title_short 
A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
title_full 
A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
title_fullStr 
A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
title_full_unstemmed 
A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
collection_title_sort_str 
(2 e)approximation scheme for minimum domination on circle graphs. 
title_sort 
(2 e)approximation scheme for minimum domination on circle graphs. 
description 
The main result of this paper is a (2 + e)approximation
scheme for the minimum dominating set problem on circle
graphs. We first present an O(n 2) time 8approximation algorithm
for the minimum dominating set problem on circle
graphs and then extend it to a (2+e)approximation scheme
that solves the minimum dominating set problem in time
O(n 3 + 6g_,f~i +l,~,~ ]. 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 + ~)
approximation schemes for the minimum connected dominating
set and the minimum total dominating set problems
on circle graphs. Keil (Discrete Applied Mathematics, 42
(1993), 5163) showed that these problems are NPcomplete
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. 
publishDate 
2002 
normalized_sort_date 
20020101T00:00:00Z 
dc_date_str 
2002 
license_str 
protected 
REPOSITORYNAME 
FgsRepos 
REPOSBASEURL 
http://hades.library.villanova.edu:8088/fedora 
fgs.state 
Active 
fgs.label 
A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
fgs.ownerId 
diglibEditor 
fgs.createdDate 
20130122T04:52:12.083Z 
fgs.lastModifiedDate 
20131205T17:10:17.390Z 
dc.title 
A (2+e)Approximation Scheme for Minimum Domination on Circle Graphs. 
dc.creator 
DamianIordache, Mirela. Pemmaraju, Sriram V. 
dc.description 
The main result of this paper is a (2 + e)approximation
scheme for the minimum dominating set problem on circle
graphs. We first present an O(n 2) time 8approximation algorithm
for the minimum dominating set problem on circle
graphs and then extend it to a (2+e)approximation scheme
that solves the minimum dominating set problem in time
O(n 3 + 6g_,f~i +l,~,~ ]. 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 + ~)
approximation schemes for the minimum connected dominating
set and the minimum total dominating set problems
on circle graphs. Keil (Discrete Applied Mathematics, 42
(1993), 5163) showed that these problems are NPcomplete
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. 
dc.date 
2002 
dc.identifier 
vudl:175632 
dc.source 
Journal of Algorithms 42(2), February 2002, 255276. 
dc.language 
en 
license.mdRef 
http://digital.library.villanova.edu/copyright.html 
agent.name 
Falvey Memorial Library, Villanova University KHL 
has_thumbnail 
true 
THUMBNAIL_contentDigest_type 
MD5 
THUMBNAIL_contentDigest_digest 
203c69e18f4f46c81e9892448d2c07cd 
THUMBNAIL_contentLocation_type 
INTERNAL_ID 
THUMBNAIL_contentLocation_ref 
http://hadesvm.library.villanova.edu:8088/fedora/get/vudl:175632/THUMBNAIL/20130122T04:52:14.215Z 
relsext.hasModel 
info:fedora/vudlsystem:CoreModel info:fedora/vudlsystem:CollectionModel info:fedora/vudlsystem:ResourceCollection 
relsext.itemID 
oai:digital.library.villanova.edu:vudl:175632 
relsext.isMemberOf 
info:fedora/vudl:175631 
relsext.hasLegacyURL 
http://digital.library.villanova.edu/Villanova%20Digital%20Collection/Faculty%20Fulltext/Damian%20Mirela/DamianMirelad399baf3ad1c4b2689990a2022aabf16.xml 
relsext.sortOn 
title 
relsext.sequence 
vudl:175631#1 
_version_ 
1644304819133874176 
score 
13.672064 
subpages 