Hardness of Approximating Independent Domination in Circle Graphs.
A graph G = (V,E) is called a circle graph if there is a one toone 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 corresponding chords in C intersect. A subset V′ of V is a dominating set of G if for all u ∈ V eith...
Main Authors:  , 

Format:  
Language:  English 
Published: 
1999

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

record_format 
vudl 
institution 
Villanova University 
collection 
Digital Library 
modeltype_str_mv 
vudlsystem:CoreModel vudlsystem:ResourceCollection vudlsystem:CollectionModel 
datastream_str_mv 
MEMBERQUERY LICENSE LEGACYMETS AUDIT RELSEXT PARENTQUERY THUMBNAIL MEMBERLISTRAW STRUCTMAP AGENTS PARENTLISTRAW DC PROCESSMD PARENTLIST 
hierarchytype 

hierarchy_all_parents_str_mv 
vudl:175631 vudl:172968 vudl:641262 vudl:3 vudl:1 
sequence_vudl_175631_str 
0000000016 
hierarchy_top_id 
vudl:641262 
hierarchy_top_title 
Villanova Faculty Publications 
fedora_parent_id_str_mv 
vudl:175631 
hierarchy_first_parent_id_str 
vudl:175680 
hierarchy_parent_id 
vudl:175631 
hierarchy_parent_title 
Damian Mirela 
hierarchy_sequence_sort_str 
0000000016 
hierarchy_sequence 
0000000016 
spelling 
Hardness of Approximating Independent Domination in Circle Graphs. DamianIordache, Mirela. Pemmaraju, Sriram V. A graph G = (V,E) is called a circle graph if there is a one toone 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 corresponding 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 no two vertices in V′ are adjacent, then V′ is called an independent dominating set; if G[V′] is connected, then V′ is called a connected dominating set. Keil (Discrete Applied Mathematics, 42 (1993), 51–63) shows that the minimum dominating set problem and the minimum connected dominating set problem are both NPcomplete even for circle graphs. He leaves open the complexity of the minimum independent dominating set problem. In this paper we show that the minimum independent dominating set problem on circle graphs is NPcomplete. Furthermore we show that for any ε, 0 ≤ ε < 1, there does not exist an n^ε approximation algorithm for the minimum independent dominating set problem on nvertex circle graphs, unless P = NP. Several other related domination problems on circle graphs are also shown to be as hard to approximate. 1999 Villanova Faculty Authorship vudl:175680 Lecture Notes in Computer Science 1741, 1999, 5969. en 
dc.title_txt_mv 
Hardness of Approximating Independent Domination in Circle Graphs. 
dc.creator_txt_mv 
DamianIordache, Mirela. Pemmaraju, Sriram V. 
dc.description_txt_mv 
A graph G = (V,E) is called a circle graph if there is a one toone 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 corresponding 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 no two vertices in V′ are adjacent, then V′ is called an independent dominating set; if G[V′] is connected, then V′ is called a connected dominating set. Keil (Discrete Applied Mathematics, 42 (1993), 51–63) shows that the minimum dominating set problem and the minimum connected dominating set problem are both NPcomplete even for circle graphs. He leaves open the complexity of the minimum independent dominating set problem. In this paper we show that the minimum independent dominating set problem on circle graphs is NPcomplete. Furthermore we show that for any ε, 0 ≤ ε < 1, there does not exist an n^ε approximation algorithm for the minimum independent dominating set problem on nvertex circle graphs, unless P = NP. Several other related domination problems on circle graphs are also shown to be as hard to approximate. 
dc.date_txt_mv 
1999 
dc.format_txt_mv 
Villanova Faculty Authorship 
dc.identifier_txt_mv 
vudl:175680 
dc.source_txt_mv 
Lecture Notes in Computer Science 1741, 1999, 5969. 
dc.language_txt_mv 
en 
author 
DamianIordache, Mirela. Pemmaraju, Sriram V. 
spellingShingle 
DamianIordache, Mirela. Pemmaraju, Sriram V. Hardness of Approximating Independent Domination in Circle Graphs. 
author_facet 
DamianIordache, Mirela. Pemmaraju, Sriram V. 
dc_source_str_mv 
Lecture Notes in Computer Science 1741, 1999, 5969. 
format 
Villanova Faculty Authorship 
author_sort 
DamianIordache, Mirela. 
dc_date_str 
1999 
dc_title_str 
Hardness of Approximating Independent Domination in Circle Graphs. 
description 
A graph G = (V,E) is called a circle graph if there is a one toone 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 corresponding 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 no two vertices in V′ are adjacent, then V′ is called an independent dominating set; if G[V′] is connected, then V′ is called a connected dominating set. Keil (Discrete Applied Mathematics, 42 (1993), 51–63) shows that the minimum dominating set problem and the minimum connected dominating set problem are both NPcomplete even for circle graphs. He leaves open the complexity of the minimum independent dominating set problem. In this paper we show that the minimum independent dominating set problem on circle graphs is NPcomplete. Furthermore we show that for any ε, 0 ≤ ε < 1, there does not exist an n^ε approximation algorithm for the minimum independent dominating set problem on nvertex circle graphs, unless P = NP. Several other related domination problems on circle graphs are also shown to be as hard to approximate. 
title 
Hardness of Approximating Independent Domination in Circle Graphs. 
title_full 
Hardness of Approximating Independent Domination in Circle Graphs. 
title_fullStr 
Hardness of Approximating Independent Domination in Circle Graphs. 
title_full_unstemmed 
Hardness of Approximating Independent Domination in Circle Graphs. 
title_short 
Hardness of Approximating Independent Domination in Circle Graphs. 
title_sort 
hardness of approximating independent domination in circle graphs. 
publishDate 
1999 
normalized_sort_date 
19990101T00:00:00Z 
language 
English 
collection_title_sort_str 
hardness of approximating independent domination in circle graphs. 
fgs.type_txt_mv 
http://www.w3.org/ns/ldp#Container http://www.w3.org/ns/ldp#BasicContainer http://www.w3.org/ns/ldp#RDFSource http://fedora.info/definitions/v4/repository#Container http://www.w3.org/ns/ldp#Resource http://fedora.info/definitions/v4/repository#Resource 
fgs.state_txt_mv 
Active 
relsext.hasModel_txt_mv 
http://hades.library.villanova.edu:8080/rest/vudlsystem:CoreModel http://hades.library.villanova.edu:8080/rest/vudlsystem:ResourceCollection http://hades.library.villanova.edu:8080/rest/vudlsystem:CollectionModel 
fgs.createdBy_txt_mv 
fedoraAdmin 
fgs.lastModifiedBy_txt_mv 
fedoraAdmin 
relsext.itemID_txt_mv 
oai:digital.library.villanova.edu:vudl:175680 
relsext.sequence_txt_mv 
vudl:175631#16 
fgs.lastModifiedDate_txt_mv 
20220819T17:51:37.003Z 
relsext.sortOn_txt_mv 
title 
relsext.isMemberOf_txt_mv 
http://hades.library.villanova.edu:8080/rest/vudl:175631 
fgs.createdDate_txt_mv 
20130122T04:54:58.859Z 
fgs.ownerId_txt_mv 
diglibEditor 
relsext.hasLegacyURL_txt_mv 
http://digital.library.villanova.edu/Villanova%20Digital%20Collection/Faculty%20Fulltext/Damian%20Mirela/DamianMirelaabfeba39ea2e40daa52a2bbc770c1778.xml 
fgs.label_txt_mv 
Hardness of Approximating Independent Domination in Circle Graphs. 
has_order_str 
no 
agent.name_txt_mv 
Falvey Memorial Library, Villanova University KHL 
license.mdRef_str 
http://digital.library.villanova.edu/copyright.html 
license_str 
protected 
has_thumbnail_str 
true 
THUMBNAIL_contentDigest_digest_str 
203c69e18f4f46c81e9892448d2c07cd 
first_indexed 
20140111T23:30:08Z 
last_indexed 
20220819T17:52:35Z 
_version_ 
1755567775920685056 
subpages 