2 citations · 2 across the 5 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
Esther Galby, Andrea Munaro, Shizhou Yang
We investigate a relaxation of the notion of fractional treewidth-fragility, namely fractional tree-independence-number-fragility. In particular, we obtain polynomial-time approxim…
cs.DS2023
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
Esther Galby, Andrea Munaro, Shizhou Yang
We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for inde…
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…