Lower bounds on the OBDD size of two fundamental functions' graphs

DOI10.1016/j.ipl.2006.08.004zbMath1185.68882OpenAlexW2080080500MaRDI QIDQ845898

Daniel Sawitzki

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.08.004

zbMATH Keywords

computational complexityanalysis of algorithmsdata structurestheory of computation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the size of binary decision diagrams representing Boolean functions
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• Branching Programs and Binary Decision Diagrams
• Algorithms and Computation
• Mathematical Foundations of Computer Science 2003
• Graph-Theoretic Concepts in Computer Science
• SOFSEM 2005: Theory and Practice of Computer Science
• SOFSEM 2004: Theory and Practice of Computer Science