The parameterized complexity of unique coverage and its variants

DOI10.1007/S00453-011-9608-0MaRDI QIDQ2392923zbMATH OpenOpenAlexFDO

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

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

hash functionsparameterized algorithmscolor codingbudgeted unique coverageunique coverage

Mathematics Subject Classification ID

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

Recommendations

• The Budgeted Unique Coverage Problem and Color-Coding
• The Parameterized Complexity of the Unique Coverage Problem
• Unique covering problems with geometric sets
• Nearly optimal NP-hardness of unique coverage
• Nearly optimal NP-hardness of unique coverage

Cites work

• scientific article; zbMATH DE number 5764844 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A hypergraph approach to the identifying parent property: The case of multiple parents
• Color-coding
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• Generalized hashing and parent-identifying codes.
• Incompressibility through Colors and IDs
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Perfect Code is \(W[1]\)-complete
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• The Budgeted Unique Coverage Problem and Color-Coding
• The Parameterized Complexity of the Unique Coverage Problem
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• The budgeted maximum coverage problem

Cited in

(15)

• A completeness theory for polynomial (Turing) kernelization
• Minimum ply covering of points with disks and squares
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• The Budgeted Unique Coverage Problem and Color-Coding
• Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs
• Exact multi-covering problems with geometric sets
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
• The Parameterized Complexity of the Unique Coverage Problem
• Local search strikes again: PTAS for variants of geometric covering and packing
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• On nonlinear multi-covering problems
• Unique covering problems with geometric sets
• Minimum ply covering of points with unit squares

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

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