The complexity of domination problems in circle graphs
type: Item
instance of: scholarly article
title: The complexity of domination problems in circle graphs
zbMATH Open document ID: 0786.05079
DOI: 10.1016/0166-218X(93)90178-Q
author: J. Mark Keil
published in: Discrete Applied Mathematics
publication date: 1993-05-16T00:00:00Z
review text: Circle graphs are the intersection graphs of chords of a circle. It is shown that the problems of finding a minimum dominating set, a minimum connected dominating set and a minimum total dominating set are NP- complete for circle graphs. A polynomial time algorithm for finding a minimum cardinality dominating clique in a circle graph is presented.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 167439
zbMATH Keywords: complexity
zbMATH Keywords: domination
zbMATH Keywords: dominating set
zbMATH Keywords: NP-complete
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: dominating clique
zbMATH Keywords: circle graphs
Wikidata QID: Q56503307
reviewed by: Maciej M. Sysło
MaRDI profile type: Publication
cites work: Finding a minimum independent dominating set in a permutation graph
cites work: Dominating Sets in Chordal Graphs
cites work: Q3694712
cites work: On domination problems for permutation and other graphs
cites work: Permutation graphs: Connected domination and Steiner trees
cites work: A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
cites work: Clustering and domination in perfect graphs
cites work: Dominating sets in perfect graphs
cites work: Q4875855
cites work: Independent domination in chordal graphs
cites work: Domination in permutation graphs
cites work: Recognizing circle graphs in polynomial time
cites work: Q4198056
cites work: Algorithms for a maximum clique and a maximum independent set of a circle graph
cites work: The NP-completeness column: an ongoing guide
cites work: Q3782805
cites work: Domination on Cocomparability Graphs
cites work: Q3791195
cites work: On the Algorithmic Complexity of Total Domination
cites work: On the Complexity of Nonconvex Covering
description: scientific article; zbMATH DE number 167439