The parameterized complexity of unique coverage and its variants

DOI10.1007/S00453-011-9608-0zbMATH Open1290.68059OpenAlexW2007225140MaRDI QIDQ2392923FDOQ2392923

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

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

zbMATH Keywords

hash functionsparameterized algorithmscolor codingbudgeted unique coverageunique coverage

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

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

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)