Branching Programs and Binary Decision Diagrams

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Analysis of algorithms and problem complexity (68Q25)

Recommendations

scientific article; zbMATH DE number 58305
scientific article; zbMATH DE number 846270
BDDs -- design, analysis, complexity, and applications.

Cited in

(only showing first 100 items - show all)

Representation of graphs by OBDDs
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
On the OBDD size for graphs of bounded tree- and clique-width
On threshold BDDs and the optimal variable ordering problem
On the P versus NP intersected with co-NP question in communication complexity
The characterization of branching dependencies
A rewriting approach to binary decision diagrams
Approximation of boolean functions by combinatorial rectangles
On uncertainty versus size in branching programs.
Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
A lower bound for integer multiplication on randomized ordered read-once branching programs.
BDDs -- design, analysis, complexity, and applications.
Optimal ordered binary decision diagrams for read-once formulas
Randomized OBDD-based graph algorithms
Exponential space complexity for OBDD-based reachability analysis
Size-treewidth tradeoffs for circuits computing the element distinctness function
Quantum branching programs and space-bounded nonuniform quantum complexity
The nonapproximability of OBDD minimization
On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
Branching constraint satisfaction problems and Markov decision problems compared
Sequential testing of complex systems: a review
On multi-partition communication complexity
On the use of binary decision diagrams for solving problems on simple games
Relation-algebraic modeling and solution of chessboard independence and domination problems
Randomized OBDDs for the most significant bit of multiplication need exponential space
Exact OBDD bounds for some fundamental functions
New size hierarchies for two way automata
A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
Outer approximation for integer nonlinear programs via decision diagrams
On the relation between structured \(d\)-DNNFs and SDDs
On Tseitin formulas, read-once branching programs and treewidth
Graph coloring with decision diagrams
Proof complexity of symbolic QBF reasoning
Two-way and one-way quantum and classical automata with advice for online minimization problems
Variable ordering for decision diagrams: a portfolio approach
Second-order finite automata
Compact representation of near-optimal integer programming solutions
Minimization problems for parity OBDDs
On the relative succinctness of sentential decision diagrams
Very narrow quantum OBDDs and width hierarchies for classical OBDDs
On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
Partition search for non-binary constraint satisfaction
Symbolic model checking for channel-based component connectors
State-set branching: leveraging BDDs for heuristic search
Theoretical insights and algorithmic tools for decision diagram-based optimization
Nondeterministic unitary OBDDs
Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
On compiling structured CNFs to OBDDs
New results on the most significant bit of integer multiplication
A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
On the OBDD complexity of the most significant bit of integer multiplication
Priority functions for the approximation of the metric TSP
A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
Symbolic topological sorting with OBDDs
Minimization of decision trees is hard to approximate
Lower bounds for restricted read-once parity branching programs
Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
State space analysis of Petri nets with relation-algebraic methods
A hierarchy result for read-once branching programs with restricted parity nondeterminism
On the influence of the variable ordering for algorithmic learning using OBDDs
The computational power of Benenson automata
Bounds on the OBDD-size of integer multiplication via universal hashing
On converting CNF to DNF
On the computational power of probabilistic and quantum branching program
\texttt{VeriSIMPL 2}: an open-source software for the verification of max-plus-linear systems
Investigating dynamic causalities in reaction systems
Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
Discrete optimization with decision diagrams
A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
Implicit computation of maximum bipartite matchings by sublinear functional operations
Computing Boolean functions via quantum hashing
An algorithm for reducing binary branchings
Optimization Bounds from Binary Decision Diagrams
Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
Randomized OBDDs for the most significant bit of multiplication need exponential size
Generic constant-round oblivious sorting algorithm for MPC
On the read-once property of branching programs and CNFs of bounded treewidth
Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
On the OBDD representation of some graph classes
Branching Programs for Tree Evaluation
On compiling structured CNFs to OBDDs
Improving OBDD attacks against stream ciphers
A comparison of BDD-based parity game solvers
A moderately exponential time algorithm for \(k\)-IBDD satisfiability
Randomized OBDD-based graph algorithms
On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
Attacking Bivium Using SAT Solvers
Extension of the hierarchy for k-OBDDs of small width
Knowledge compilation meets database theory: compiling queries to decision diagrams
On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
Larger Lower Bounds on the OBDD Complexity of Integer Multiplication
scientific article; zbMATH DE number 58305 (Why is no real title available?)
scientific article; zbMATH DE number 512863 (Why is no real title available?)
On symbolic OBDD-based algorithms for the minimum spanning tree problem
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
Symbolic bounded synthesis
On efficient implicit OBDD-based algorithms for maximal matchings
Implicit computation of maximum bipartite matchings by sublinear functional operations
Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs

This page was built for publication: Branching Programs and Binary Decision Diagrams

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