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 8-approximation 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), 51-63) 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.

Main Author: Damian-Iordache, 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 vudl-system:CoreModel
vudl-system:CollectionModel
vudl-system:ResourceCollection
datastream_str_mv DC
PARENT-QUERY
PARENT-LIST-RAW
PARENT-LIST
MEMBER-QUERY
MEMBER-LIST-RAW
LEGACY-METS
LICENSE
AGENTS
PROCESS-MD
THUMBNAIL
STRUCTMAP
RELS-EXT
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 2014-01-11T23:30:12Z
last_indexed 2014-01-11T23: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, 255-276.
author Damian-Iordache, Mirela.
author_facet_str_mv Damian-Iordache, Mirela.
Pemmaraju, Sriram V.
author_or_contributor_facet_str_mv Damian-Iordache, Mirela.
Pemmaraju, Sriram V.
author_s Damian-Iordache, Mirela.
spellingShingle Damian-Iordache, Mirela.
A (2+e)-Approximation Scheme for Minimum Domination on Circle Graphs.
author-letter Damian-Iordache, Mirela.
author_sort_str Damian-Iordache, 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 8-approximation 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), 51-63) 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.
publishDate 2002
normalized_sort_date 2002-01-01T00: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 2013-01-22T04:52:12.083Z
fgs.lastModifiedDate 2013-12-05T17:10:17.390Z
dc.title A (2+e)-Approximation Scheme for Minimum Domination on Circle Graphs.
dc.creator Damian-Iordache, 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 8-approximation 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), 51-63) 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.
dc.date 2002
dc.identifier vudl:175632
dc.source Journal of Algorithms 42(2), February 2002, 255-276.
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://hades-vm.library.villanova.edu:8088/fedora/get/vudl:175632/THUMBNAIL/2013-01-22T04:52:14.215Z
relsext.hasModel info:fedora/vudl-system:CoreModel
info:fedora/vudl-system:CollectionModel
info:fedora/vudl-system: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/DamianMirela-d399baf3-ad1c-4b26-8999-0a2022aabf16.xml
relsext.sortOn title
relsext.sequence vudl:175631#1
_version_ 1644304819133874176
score 13.672064
subpages