Jul 2026
The Minimum Dominating Set Problem on Bipartite Circle Graphs: Complexity and Approximation
It is proved that the problem of computing a minimum dominating set on bipartite circle graphs admitting a chord representation in which the chords can be partitioned into two color classes such that no two chords of the same color intersect remains NP-hard.
A. K. Abu-Affash, Paz Carmi, Joseph S. B. Mitchell
· arXiv.org · 0 citations