Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
From MaRDI portal
Publication:841618
DOI10.1007/S00224-007-9067-9zbMath1175.68121OpenAlexW2095578678WikidataQ57601473 ScholiaQ57601473MaRDI QIDQ841618
Publication date: 18 September 2009
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-007-9067-9
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Cites Work
- Neither reading few bits twice nor reading illegally helps much
- Time-space tradeoffs for branching programs
- On lower bounds for read-\(k\)-times branching programs
- Determinism versus non-determinism for linear time RAMs (extended abstract)
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Time-space trade-off lower bounds for randomized computation of decision problems
- On the complexity of branching programs and decision trees for clique functions
- Branching Programs and Binary Decision Diagrams
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
