Counterexamples to the long-standing conjecture on the complexity of BDD binary operations
DOI10.1016/J.IPL.2012.05.007zbMATH Open1248.68265OpenAlexW2099887511WikidataQ122922539 ScholiaQ122922539MaRDI QIDQ456068FDOQ456068
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
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
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)
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)
- 0/1 vertex and facet enumeration with BDDs
- A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
- Correctness and concurrent complexity of the black-white bakery algorithm
- Efficient symbolic search for cost-optimal planning
- Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
Uses Software
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)
