Graph-driven free parity BDDs: Algorithms and lower bounds

DOI10.1007/3-540-44683-4_19MaRDI QIDQ4779145zbMATH OpenFDO

Authors Henrik Brosenne, Matthias Homeister, Stephan Waack

Publication date 25 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2136/21360212

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
• Algebraic and uniqueness properties of parity ordered binary decision diagrams and their generalization (extended abstract)
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• Graph driven BDDs -- a new data structure for Boolean functions
• On the descriptive and algorithmic power of parity ordered binary decision diagrams

Cited in

(5)

• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• Lower bounds for restricted read-once parity branching programs
• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
• Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
• 0/1 vertex and facet enumeration with BDDs

This page was built for publication: Graph-driven free parity BDDs: Algorithms and lower bounds

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