Hardness of Approximating Independent Domination in Circle Graphs.
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 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 |
vudl-system:CoreModel vudl-system:ResourceCollection vudl-system:CollectionModel |
| datastream_str_mv |
MEMBER-QUERY LICENSE LEGACY-METS AUDIT RELS-EXT PARENT-QUERY THUMBNAIL MEMBER-LIST-RAW STRUCTMAP AGENTS PARENT-LIST-RAW DC PROCESS-MD PARENT-LIST |
| 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. Damian-Iordache, Mirela. Pemmaraju, Sriram V. 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 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 NP-complete 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 NP-complete. Furthermore we show that for any ε, 0 ≤ ε < 1, there does not exist an n^ε -approximation algorithm for the minimum independent dominating set problem on n-vertex 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, 59-69. en |
| dc.title_txt_mv |
Hardness of Approximating Independent Domination in Circle Graphs. |
| dc.creator_txt_mv |
Damian-Iordache, Mirela. Pemmaraju, Sriram V. |
| dc.description_txt_mv |
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 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 NP-complete 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 NP-complete. Furthermore we show that for any ε, 0 ≤ ε < 1, there does not exist an n^ε -approximation algorithm for the minimum independent dominating set problem on n-vertex 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, 59-69. |
| dc.language_txt_mv |
en |
| author |
Damian-Iordache, Mirela. Pemmaraju, Sriram V. |
| spellingShingle |
Damian-Iordache, Mirela. Pemmaraju, Sriram V. Hardness of Approximating Independent Domination in Circle Graphs. |
| author_facet |
Damian-Iordache, Mirela. Pemmaraju, Sriram V. |
| dc_source_str_mv |
Lecture Notes in Computer Science 1741, 1999, 59-69. |
| format |
Villanova Faculty Authorship |
| author_sort |
Damian-Iordache, 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- 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 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 NP-complete 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 NP-complete. Furthermore we show that for any ε, 0 ≤ ε < 1, there does not exist an n^ε -approximation algorithm for the minimum independent dominating set problem on n-vertex 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 |
1999-01-01T00: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/vudl-system:CoreModel http://hades.library.villanova.edu:8080/rest/vudl-system:ResourceCollection http://hades.library.villanova.edu:8080/rest/vudl-system: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 |
2022-08-19T17: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 |
2013-01-22T04:54:58.859Z |
| fgs.ownerId_txt_mv |
diglibEditor |
| relsext.hasLegacyURL_txt_mv |
http://digital.library.villanova.edu/Villanova%20Digital%20Collection/Faculty%20Fulltext/Damian%20Mirela/DamianMirela-abfeba39-ea2e-40da-a52a-2bbc770c1778.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 |
2014-01-11T23:30:08Z |
| last_indexed |
2022-08-19T17:52:35Z |
| _version_ |
1755567775920685056 |
| subpages |