A note on the size of OBDDs for the graph of integer multiplication
type: Item
instance of: scholarly article
title: A note on the size of OBDDs for the graph of integer multiplication
zbMATH Open document ID: 1193.68128
author: Beate Bollig
published in: Information Processing Letters
publication date: 2010-06-09T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5719234
zbMATH Keywords: computational complexity
zbMATH Keywords: integer multiplicaton
zbMATH Keywords: lower bounds
zbMATH Keywords: ordered binary decision diagrams
MaRDI profile type: Publication
full work available at URL: j.ipl.2008.08.008
OpenAlex ID: W2074097193
cites work: Better upper bounds on the QOBDD size of integer multiplication
cites work: On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
cites work: A read-once branching program lower bound of Ω(2 n/4 ) for integer multiplication using universal hashing
cites work: Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
cites work: Q3549597
cites work: Q4471346
cites work: Q4337605
cites work: Communication Complexity
cites work: A Lower Bound for Integer Multiplication with Read-Once Branching Programs
cites work: Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
cites work: SOFSEM 2005: Theory and Practice of Computer Science
cites work: Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
cites work: Bounds on the OBDD-size of integer multiplication via universal hashing
DOI: 10.1016/J.IPL.2008.08.008
description: scientific article; zbMATH DE number 5719234