The parameterized complexity of unique coverage and its variants

DOI10.1007/s00453-011-9608-0zbMath1290.68059OpenAlexW2007225140MaRDI QIDQ2392923

Somnath Sikdar, Neeldhara Misra, Venkatesh Raman, Hannes Moser, Saket Saurabh

Publication date: 5 August 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9608-0

zbMATH Keywords

parameterized algorithmshash functionscolor codingbudgeted unique coverageunique coverage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Related Items (11)

Minimum ply covering of points with disks and squares ⋮ Unique Covering Problems with Geometric Sets ⋮ Minimum ply covering of points with unit squares ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ On nonlinear multi-covering problems ⋮ A 4.31-approximation for the geometric unique coverage problem on unit disks ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ The Budgeted Unique Coverage Problem and Color-Coding ⋮ Exact multi-covering problems with geometric sets ⋮ A completeness theory for polynomial (Turing) kernelization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Generalized hashing and parent-identifying codes.
• Perfect Code is \(W[1\)-complete]
• The budgeted maximum coverage problem
• A Hypergraph Approach to the Identifying Parent Property: The Case of Multiple Parents
• The Budgeted Unique Coverage Problem and Color-Coding
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Incompressibility through Colors and IDs
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Color-coding
• The Parameterized Complexity of the Unique Coverage Problem

This page was built for publication: The parameterized complexity of unique coverage and its variants