Hardness results and approximation schemes for discrete packing and domination problems

DOI10.1007/978-3-030-04651-4_28MaRDI QIDQ2327121zbMATH OpenOpenAlexFDO

Authors Raghunath Reddy Madireddy, Apurva Mudgal, Supantha Pandit

Publication date 11 October 2019

Full work available at URL https://doi.org/10.1007/978-3-030-04651-4_28

zbMATH Keywords

local searchdisksaxis-parallel rectanglesdiscrete dominating setdiscrete independent set\(\mathsf{APX}\)-hard\(\mathsf{PTAS}\mathsf{NP}\)-hardaxis-parallel squares

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• Maximum independent and disjoint coverage
• Domination in Geometric Intersection Graphs
• Dominating set of rectangles intersecting a straight line
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Maximum area independent sets in disk intersection graphs

Cited in

(3)

• Dominating set of rectangles intersecting a straight line
• Complexity results for the horizontal bar packing problem
• Maximum independent and disjoint coverage

This page was built for publication: Hardness results and approximation schemes for discrete packing and domination problems

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