2 papers
cs.DS2026
Dominating Set with Quotas: Balancing Coverage and Constraints
Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh +2
We study a natural generalization of the classical \textsc{Dominating Set} problem, called \textsc{Dominating Set with Quotas} (DSQ). In this problem, we are given a graph \( G \),…
cs.CG2026
Line Cover and Related Problems
Matthias Bentert, Fedor v. Fomin, Petr A. Golovach +4
We study extensions of the classic \emph{Line Cover} problem, which asks whether a set of points in the plane can be covered using lines. Line Cover is known to be NP-hard,…