| Article ID: | iaor1994251 |
| Country: | Netherlands |
| Volume: | 42 |
| Issue: | 1 |
| Start Page Number: | 51 |
| End Page Number: | 63 |
| Publication Date: | Feb 1993 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Keil Mark J. |
| Keywords: | NP-complete |
Circle graphs are the intersection graphs of chords of a circle. This paper shows 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. It also presents a polynomial time algorithm for finding a minimum cardinality dominating clique in a circle graph.