Unique covering problems with geometric sets

DOI10.1007/978-3-319-21398-9_43MaRDI QIDQ3196414zbMATH OpenOpenAlexFDO

Authors Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra, Saket Saurabh

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21398-9_43

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Applications of graph theory to circuits and networks (94C15)

Recommendations

• The Parameterized Complexity of the Unique Coverage Problem
• Local search strikes again: PTAS for variants of geometric covering and packing
• Local search strikes again: PTAS for variants of geometric covering and packing
• The parameterized complexity of unique coverage and its variants
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares

Cites work

• Algorithms – ESA 2005
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• Covering things with things
• Fast approximation algorithms for a nonconvex covering problem
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• Kernelization lower bounds through colors and IDs
• On the complexity of locating linear facilities in the plane
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Parametrized complexity theory.
• PTAS for geometric hitting set problems via local search
• Reducibility among combinatorial problems
• The parameterized complexity of unique coverage and its variants

Cited in

(7)

• Exact multi-covering problems with geometric sets
• Geometric red-blue set cover for unit squares and related problems
• The parameterized complexity of unique coverage and its variants
• The Parameterized Complexity of the Unique Coverage Problem
• Local search strikes again: PTAS for variants of geometric covering and packing
• P versus NPC: minimum Steiner trees in convex split graphs
• On convexity in split graphs: complexity of Steiner tree and domination

This page was built for publication: Unique covering problems with geometric sets

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