Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph

DOI10.1016/j.tcs.2022.07.039OpenAlexW4289778941WikidataQ114129052 ScholiaQ114129052MaRDI QIDQ2674709

Zhao Zhang, Weizhi Hong, Yingli Ran

Publication date: 14 September 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.07.039

zbMATH Keywords

parallel algorithmapproximation ratiounit disk graphpartial dominating setbudgeted dominating set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved performance of the greedy algorithm for partial cover
• Connected dominating set. Theory and applications
• Unit disk cover problem in 2D
• On approximation problems related to the independent set and vertex cover problems
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• A better constant-factor approximation for weighted dominating set in unit disk graph
• Optimal packing and covering in the plane are NP-complete
• Unit disk graphs
• Covering a set of points in multidimensional space
• The budgeted maximum coverage problem
• Parallel approximation for partial set cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• A PTAS for the Weighted Unit Disk Cover Problem
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• The Maximum Coverage Location Problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Approximation algorithms for partial covering problems
• An efficient distributed algorithm for constructing small dominating sets
• Deterministic Distributed Dominating Set Approximation in the CONGEST Model
• Analytical approach to parallel repetition
• ON THE DISCRETE UNIT DISK COVER PROBLEM
• Partial vs. Complete Domination: t-Dominating Set
• Approximation and Online Algorithms
• Constant-time distributed dominating set approximation