PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
From MaRDI portal
Publication:1706122
DOI10.1016/j.dam.2017.12.039zbMath1382.05037MaRDI QIDQ1706122
Yishuo Shi, Xiaosong Li, Xiao-hui Huang
Publication date: 21 March 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2017.12.039
local search; PTAS; disk graph; \(k\)-path vertex cover; node deletion problem; connected \(k\)-subgraph cover; degree-bounded node deletion; maximum subgraph problem
05C35: Extremal problems in graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C40: Connectivity