The parameterized complexity of unique coverage and its variants
type: Item
instance of: scholarly article
title: The parameterized complexity of unique coverage and its variants
zbMATH Open document ID: 1290.68059
author: Neeldhara Misra
author: Hannes Moser
author: Venkatesh Raman
author: Saket Saurabh
author: Somnath Sikdar
published in: Algorithmica
publication date: 2013-08-05T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6194533
zbMATH Keywords: parameterized algorithms
zbMATH Keywords: unique coverage
zbMATH Keywords: budgeted unique coverage
zbMATH Keywords: color coding
zbMATH Keywords: hash functions
MaRDI profile type: Publication
full work available at URL: s00453-011-9608-0
OpenAlex ID: W2007225140
cites work: Color-coding
cites work: Generalized hashing and parent-identifying codes.
cites work: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
cites work: A hypergraph approach to the identifying parent property: The case of multiple parents
cites work: Perfect Code is \(W[1]\)-complete
cites work: Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
cites work: Combination Can Be Hard: Approximability of the Unique Coverage Problem
cites work: Incompressibility through Colors and IDs
cites work: Q3579437
cites work: The budgeted maximum coverage problem
cites work: The Budgeted Unique Coverage Problem and Color-Coding
cites work: The Parameterized Complexity of the Unique Coverage Problem
cites work: Q4856179
cites work: Q5710169
cites work: The Spatial Complexity of Oblivious k-Probe Hash Functions
DOI: 10.1007/S00453-011-9608-0
description: scientific article