Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs

DOI10.1016/J.TCS.2020.06.020MaRDI QIDQ2193275zbMATH OpenOpenAlexFDO

Authors Pengcheng Liu, Zhao Zhang, Xiaohui 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

zbMATH Keywords

approximation algorithmunit disk graph\(k\)-bounded-degree node deletion problemconnected \(k\)-bounded-degree node deletion problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Signed and weighted graphs (05C22) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Approximating bounded degree deletion via matroid matching
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• A better constant-factor approximation for weighted dominating set in unit disk graph
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

Cites work

• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
• A NEW PROOF FOR ZASSENHAUS–GROEMER–OLER INEQUALITY
• A better approximation ratio for the vertex cover problem
• A factor 2 approximation algorithm for the vertex cover P₃ problem
• A generalization of Nemhauser and Trotter's local optimization theorem
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• A new approach for approximating node deletion problems
• A parameterized algorithm for bounded-degree vertex deletion
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network
• A unified approximation algorithm for node-deletion problems
• An inequality in the geometry of numbers
• Approximating bounded degree deletion via matroid matching
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• Every property of hyperfinite graphs is testable
• Graph theory
• On approximability of connected path vertex cover
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On structural parameterizations of the bounded-degree vertex deletion problem
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Property testing in bounded degree graphs
• The node-deletion problem for hereditary properties is NP-complete
• The vertex cover \(P_3\) problem in cubic graphs

Cited in

(2)

• A unified local ratio approximation of node-deletion problems
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs

This page was built for publication: Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2193275)