The Budgeted Unique Coverage Problem and Color-Coding

DOI10.1007/978-3-642-03351-3_29MaRDI QIDQ3392967zbMATH OpenOpenAlexFDO

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

Publication date 18 August 2009

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03351-3_29

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20)

Recommendations

• The parameterized complexity of unique coverage and its variants
• The Parameterized Complexity of the Unique Coverage Problem
• Balanced hashing, color coding and approximate counting
• Balanced Families of Perfect Hash Functions and Their Applications
• Balanced families of perfect hash functions and their applications

Cites work

• scientific article; zbMATH DE number 5764844 (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?)
• A hypergraph approach to the identifying parent property: The case of multiple parents
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Color-coding
• Combination can be hard
• Generalized hashing and parent-identifying codes.
• Improved algorithms for path, matching, and packing problems
• The Parameterized Complexity of the Unique Coverage Problem
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• The budgeted maximum coverage problem
• The parameterized complexity of unique coverage and its variants

Cited in

(6)

• Budgeted colored matching problems
• The parameterized complexity of unique coverage and its variants
• Confronting intractability via parameters
• Balanced hashing, color coding and approximate counting
• The Parameterized Complexity of the Unique Coverage Problem
• On nonlinear multi-covering problems

This page was built for publication: The Budgeted Unique Coverage Problem and Color-Coding

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