Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
DOI10.1016/j.tcs.2020.06.020zbMath1452.68139OpenAlexW3040415188MaRDI QIDQ2193275
Pengcheng Liu, Zhao Zhang, Xiao-hui Huang
Publication date: 25 August 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.06.020
approximation algorithmunit disk graph\(k\)-bounded-degree node deletion problemconnected \(k\)-bounded-degree node deletion problem
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62) Signed and weighted graphs (05C22)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
- 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
- A generalization of Nemhauser and Trotter's local optimization theorem
- A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
- An inequality in the geometry of numbers
- 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
- On approximability of connected path vertex cover
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Approximation algorithms for minimum weight connected 3-path vertex cover
- PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
- The vertex cover \(P_3\) problem in cubic graphs
- A Parameterized Algorithm for Bounded-Degree Vertex Deletion
- Every Property of Hyperfinite Graphs Is Testable
- A NEW PROOF FOR ZASSENHAUS–GROEMER–OLER INEQUALITY
- 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
- A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
- On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
- Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
- Approximating Bounded Degree Deletion via Matroid Matching
- Property testing in bounded degree graphs
This page was built for publication: Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
