The Minimum Dominating Set Problem on Bipartite Circle Graphs: Complexity and Approximation

A. Karim Abu-Affash, Paz Carmi, Joseph S. B. Mitchell

A circle graph is the intersection graph of a set of chords in a circle. A dominating set of a graph $G=(V,E)$ is a subset $D\subseteq V$ such that every vertex in $V\setminus D$ i…