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

DOI10.1016/J.IPL.2006.08.004MaRDI QIDQ845898zbMATHOpenAlexFDO

Authors 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

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

Recommendations

• SOFSEM 2005: Theory and Practice of Computer Science
• Exact OBDD bounds for some fundamental functions
• Exact OBDD Bounds for Some Fundamental Functions
• On the size of (generalized) OBDDs for threshold functions
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms

Cites work

• scientific article; zbMATH DE number 1688393 (Why is no real title available?)
• scientific article; zbMATH DE number 2079387 (Why is no real title available?)
• scientific article; zbMATH DE number 918600 (Why is no real title available?)
• Algorithms and Computation
• Branching Programs and Binary Decision Diagrams
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Graph-Theoretic Concepts in Computer Science
• Mathematical Foundations of Computer Science 2003
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• On the size of binary decision diagrams representing Boolean functions
• SOFSEM 2004: Theory and Practice of Computer Science
• SOFSEM 2005: Theory and Practice of Computer Science

Cited in

(7)

• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• On the OBDD size for graphs of bounded tree- and clique-width
• scientific article; zbMATH DE number 1670823 (Why is no real title available?)
• Exact OBDD bounds for some fundamental functions
• Exact OBDD Bounds for Some Fundamental Functions
• SOFSEM 2005: Theory and Practice of Computer Science
• On the OBDD representation of some graph classes

This page was built for publication: Lower bounds on the OBDD size of two fundamental functions' graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845898)