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

DOI10.1016/j.ipl.2012.05.007zbMath1248.68265OpenAlexW2099887511WikidataQ122922539 ScholiaQ122922539MaRDI QIDQ456068

Hiroki Arimura, Ryo Yoshinaka, Shuhei Denzumi, 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) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30) Data structures (68P05)

Related Items

Efficient symbolic search for cost-optimal planning, A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm

Uses Software

• CUDD

Cites Work

• Graph-Based Algorithms for Boolean Function Manipulation
• Unnamed Item