A note on the size of OBDDs for the graph of integer multiplication

DOI10.1016/J.IPL.2008.08.008zbMath1193.68128OpenAlexW2074097193MaRDI QIDQ975522

Beate Bollig

Publication date: 9 June 2010

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

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

zbMATH Keywords

computational complexityordered binary decision diagramslower boundsinteger multiplicaton

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (2)

Larger lower bounds on the OBDD complexity of integer multiplication ⋮ Larger Lower Bounds on the OBDD Complexity of Integer Multiplication

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Better upper bounds on the QOBDD size of integer multiplication
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• Bounds on the OBDD-size of integer multiplication via universal hashing
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Graph-Based Algorithms for Boolean Function Manipulation
• A Lower Bound for Integer Multiplication with Read-Once Branching Programs
• Communication Complexity
• A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing
• SOFSEM 2005: Theory and Practice of Computer Science

This page was built for publication: A note on the size of OBDDs for the graph of integer multiplication