Unique Covering Problems with Geometric Sets

DOI10.1007/978-3-319-21398-9_43zbMath1391.68103OpenAlexW2271833894MaRDI QIDQ3196414

Saket Saurabh, Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra

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

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

Related Items (5)

P versus NPC: minimum Steiner trees in convex split graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ Approximability of covering cells with line segments ⋮ Exact multi-covering problems with geometric sets

Cites Work

• Unnamed Item
• On the complexity of locating linear facilities in the plane
• The parameterized complexity of unique coverage and its variants
• Covering things with things
• Parametrized complexity theory.
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• Fast approximation algorithms for a nonconvex covering problem
• Kernelization Lower Bounds Through Colors and IDs
• Reducibility among Combinatorial Problems
• PTAS for geometric hitting set problems via local search
• Algorithms – ESA 2005
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: Unique Covering Problems with Geometric Sets