A constant-factor approximation algorithm for red-blue set cover with unit disks

DOI10.1007/s00453-022-01012-zOpenAlexW4289774630WikidataQ114229322 ScholiaQ114229322MaRDI QIDQ5925710

Apurva Mudgal, Raghunath Reddy Madireddy

Publication date: 21 April 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01012-z

zbMATH Keywords

sweep-line methodunit disksred-blue set coverline-separablestrip-separable

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unit disk cover problem in 2D
• The within-strip discrete unit disk cover problem
• Improved results on geometric hitting set problems
• Optimal packing and covering in the plane are NP-complete
• Geometric red-blue set cover for unit squares and related problems
• On the Discrete Unit Disk Cover Problem
• A PTAS for the Weighted Unit Disk Cover Problem
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Covering Points by Unit Disks of Fixed Location
• A constant-factor approximation algorithm for red-blue set cover with unit disks

This page was built for publication: A constant-factor approximation algorithm for red-blue set cover with unit disks