Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice

DOI10.1007/S00224-007-9067-9zbMath1175.68121OpenAlexW2095578678WikidataQ57601473 ScholiaQ57601473MaRDI QIDQ841618

Daniel Král'

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

zbMATH Keywords

binary decision diagramsfree binary decision diagrams

Mathematics Subject Classification ID

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