Counterexamples to the long-standing conjecture on the complexity of BDD binary operations

DOI10.1016/J.IPL.2012.05.007MaRDI QIDQ456068zbMATH OpenOpenAlexWikidataFDO

Authors Ryo Yoshinaka, Shuhei Denzumi, Hiroki Arimura, Jun Kawahara, Shin-Ichi Minato

Publication date 23 October 2012

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

Full work available at URL http://hdl.handle.net/2115/50105

zbMATH Keywords

analysis of algorithmsdata structuresbinary decision diagram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05) Boolean functions (06E30)

Recommendations

• A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
• BDDs -- design, analysis, complexity, and applications.
• On the structure of counterexamples to symmetric orderings for BDD's
• On the size of binary decision diagrams representing Boolean functions
• scientific article; zbMATH DE number 1948534

Cites work

• Graph-Based Algorithms for Boolean Function Manipulation
• The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.

Cited in

(5)

• Efficient symbolic search for cost-optimal planning
• A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
• Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
• Correctness and concurrent complexity of the black-white bakery algorithm
• 0/1 vertex and facet enumeration with BDDs

Describes a project that uses

Uses Software

• CUDD

This page was built for publication: Counterexamples to the long-standing conjecture on the complexity of BDD binary operations

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