A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm

DOI10.1016/j.ipl.2013.11.003zbMath1284.68209OpenAlexW2086361927WikidataQ122987287 ScholiaQ122987287MaRDI QIDQ2445400

Beate Bollig

Publication date: 14 April 2014

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.11.003

zbMATH Keywords

computational complexityanalysis of algorithmsordered binary decision diagrams

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Boolean functions (06E30) Data structures (68P05)

Related Items (1)

Efficient symbolic search for cost-optimal planning

Uses Software

• CUDD

Cites Work

• Counterexamples to the long-standing conjecture on the complexity of BDD binary operations
• Exact OBDD bounds for some fundamental functions
• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems

This page was built for publication: A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm