The complexity of domination problems in circle graphs
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.
scientific article; zbMATH DE number 167439
scientific article