Balanced hashing, color coding and approximate counting

DOI10.1007/978-3-642-11269-0_1MaRDI QIDQ3656847zbMATH OpenOpenAlexFDO

Authors Noga Alon, Shai Gutner

Publication date 14 January 2010

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-11269-0_1

zbMATH Keywords

\(k\)-wise independenceapproximate counting of subgraphscolor-codingderandomizationexpandersperfect hashing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Genetics and epigenetics (92D10)

Recommendations

• Balanced Families of Perfect Hash Functions and Their Applications
• Balanced families of perfect hash functions and their applications
• Color-coding
• Approximate counting by hashing in bounded arithmetic
• The Budgeted Unique Coverage Problem and Color-Coding

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Algorithm engineering for color-coding with applications to signaling pathway detection
• An Elementary Construction of Constant-Degree Expanders
• Balanced Families of Perfect Hash Functions and Their Applications
• Color-coding
• Counting Paths and Packings in Halves
• Expander graphs and their applications
• Finding and counting given length cycles
• Finding, minimizing, and counting weighted subgraphs
• scientific article; zbMATH DE number 3943824 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• On the complexity of k-SAT
• Random Cayley graphs and expanders
• Simple Constructions of Almost k-wise Independent Random Variables
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The Parameterized Complexity of Counting Problems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Which problems have strongly exponential complexity?

Cited in

(9)

• Sublinear-time algorithms for counting star subgraphs via edge sampling
• Maximum disjoint paths on edge-colored graphs: approximability and tractability
• Balanced families of perfect hash functions and their applications
• The Budgeted Unique Coverage Problem and Color-Coding
• Counting problems in parameterized complexity
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• The \(k\)-distinct language: parameterized automata constructions
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
• The challenges of unbounded treewidth in parameterised subgraph counting problems

This page was built for publication: Balanced hashing, color coding and approximate counting

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