Showing cs.CGShow all
2 papers · 1 filter
cs.CG2026
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 is a subset such that every vertex in i…
cs.CG2024
Robustly Guarding Polygons
Rathish Das, Omrit Filtser, Matthew J. Katz +1
We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point gua…