PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
From MaRDI portal
Publication:1706122
DOI10.1016/j.dam.2017.12.039zbMath1382.05037OpenAlexW2794290187MaRDI 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 searchPTASdisk graph\(k\)-path vertex covernode deletion problemconnected \(k\)-subgraph coverdegree-bounded node deletionmaximum subgraph problem
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)
Related Items
Computing connected-\(k\)-subgraph cover with connectivity requirement, Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
Cites Work
- Unnamed Item
- Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
- On the weighted \(k\)-path vertex cover problem
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- PTAS for minimum \(k\)-path vertex cover in ball graph
- A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Improved results on geometric hitting set problems
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- On bounded-degree vertex deletion parameterized by treewidth
- A new approach for approximating node deletion problems
- The node-deletion problem for hereditary properties is NP-complete
- A unified approximation algorithm for node-deletion problems
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- On the \(k\)-path vertex cover of some graph products
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Minimum vertex cover in ball graphs through local search
- Minimum \(k\)-path vertex cover
- The \(k\)-path vertex cover of rooted product graphs
- Faster parameterized algorithms for deletion to split graphs
- PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
- Narrow sieves for parameterized paths and packings
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- The vertex cover \(P_3\) problem in cubic graphs
- On the vertex \(k\)-path cover
- Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
- A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
- A 2-approximation algorithm for the vertex coverP4problem in cubic graphs
- A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
- Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- Node-Deletion NP-Complete Problems
- Node-Deletion Problems on Bipartite Graphs
- Separators for sphere-packings and nearest neighbor graphs
- The approximation of maximum subgraph problems
- Approximating Bounded Degree Deletion via Matroid Matching
- Approximation algorithms for maximum independent set of pseudo-disks
