The Parameterized Complexity of the Unique Coverage Problem

DOI10.1007/978-3-540-77120-3_54MaRDI QIDQ5387796zbMATH OpenOpenAlexFDO

Authors Hannes Moser, Venkatesh Raman, Somnath Sikdar

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_54

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The parameterized complexity of unique coverage and its variants
• Unique covering problems with geometric sets
• The Budgeted Unique Coverage Problem and Color-Coding
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• On efficient fixed-parameter algorithms for weighted vertex cover

Cites work

• Combination can be hard
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Non deterministic polynomial optimization problems and their approximations
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization

Cited in

(9)

• A 4.31-approximation for the geometric unique coverage problem on unit disks
• The parameterized complexity of unique coverage and its variants
• Parameterized complexity of Eulerian deletion problems
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Unique covering problems with geometric sets
• The Budgeted Unique Coverage Problem and Color-Coding
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• On nonlinear multi-covering problems
• Parameterized complexity of conflict-free set cover

This page was built for publication: The Parameterized Complexity of the Unique Coverage Problem

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