3 papers
cs.DS2020
Approximating Independent Set and Dominating Set on VPG graphs
Esther Galby, Andrea Munaro
We consider Independent Set and Dominating Set restricted to VPG graphs (or, equivalently, string graphs). We show that they both remain -hard on -VPG graphs admi…
cs.CG2019
CPG graphs: Some structural and hardness results
Nicolas Champseix, Esther Galby, Andrea Munaro +1
In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in [Deniz et al., 2018]. A CPG graph is a graph for which there exists a…
cs.CC2018
Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Esther Galby, Andrea Munaro, Bernard Ries
A semitotal dominating set of a graph with no isolated vertex is a dominating set of such that every vertex in is within distance two of another vertex in . The…