PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs

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

zbMATH Keywords

local searchPTASdisk graph\(k\)-path vertex covernode deletion problemconnected \(k\)-subgraph coverdegree-bounded node deletionmaximum subgraph problem

Mathematics Subject Classification ID

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 coverP₄problem 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