Balanced Hashing, Color Coding and Approximate Counting
From MaRDI portal
Publication:3656847
DOI10.1007/978-3-642-11269-0_1zbMath1273.68270OpenAlexW2152732502MaRDI QIDQ3656847
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
derandomizationexpanderscolor-coding\(k\)-wise independenceperfect hashingapproximate counting of subgraphs
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)
Related Items (7)
The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings ⋮ Unnamed Item ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Maximum disjoint paths on edge-colored graphs: approximability and tractability ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting given length cycles
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Which problems have strongly exponential complexity?
- The Spatial Complexity of Oblivious k-Probe Hash Functions
- Expander graphs and their applications
- An Elementary Construction of Constant-Degree Expanders
- Counting Paths and Packings in Halves
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Simple Constructions of Almost k-wise Independent Random Variables
- Random Cayley graphs and expanders
- Color-coding
- The Parameterized Complexity of Counting Problems
- Finding, minimizing, and counting weighted subgraphs
- Balanced Families of Perfect Hash Functions and Their Applications
- On the complexity of \(k\)-SAT
This page was built for publication: Balanced Hashing, Color Coding and Approximate Counting
