Complement Edges in BDD
ConceptComplement edges are a BDD representation technique that allows a node to represent both a Boolean function and its complement by marking the incoming edge rather than adding a negated subgraph, enabling reduced, ordered BDDs to contain only the 1-terminal.
First seen 7/13/2026
Last seen 7/13/2026
Evidence 2 chunks
Wiki v1
WIKI
Complement Edges in BDD
Definition
A Binary Decision Diagram (BDD) is an ordered directed acyclic graph in which each variable is encountered at most once on every root-to-terminal path and the variable order is consistent across all such paths. A BDD is reduced if it contains no isomorphic subgraphs and no redundant nodes. A reduced and ordered BDD (ROBDD) is a canonical representation of a Boolean function.
NEIGHBORHOOD
No graph connections found for this entity yet. It may appear in future ingestion runs.
explore full graph →RELATIONSHIPS
2 connectionsThe BDD representation used by the weighting algorithm employs complement edges.
BDDs can be shown using complement edges to represent both a function and its complement.
CITATIONS
8 sources8 citations — click to expand
[1] A BDD is called ordered if each variable is encountered at most once on each path from the root to a terminal and the variable order is consistent across paths. Improvements for Constraint Solving in the SCV Library
[2] A BDD is called reduced if it contains neither isomorphic subgraphs nor redundant nodes; reduced and ordered BDDs are a canonical representation of a Boolean function. Improvements for Constraint Solving in the SCV Library
[3] The BDD for f = x1*x2 + x1*x2*x3 shown in Figure 3 is drawn using complement edges, allowing both the function and its complement to be represented by the same node by modifying the edge instead, so the diagram contains only the 1-terminal. Improvements for Constraint Solving in the SCV Library
[4] The intuitive traversal probability for the 1-edge of the root node in the example BDD should be corrected to 33% instead of 50% to achieve a uniform distribution of solutions. Improvements for Constraint Solving in the SCV Library
[5] The SCV constraint solver implements a recursive weighting algorithm in a pre-processing step that traverses the initial constraint BDD, computes weights for the else- and then-children while accounting for nodes removed by BDD reduction rules, and assigns a probability to each BDD node. Improvements for Constraint Solving in the SCV Library
[6] The SCV constraint solver calls the weighting algorithm only once at the beginning on the initial constraint BDD, so subsequent simplifications such as fixing variables leave the probabilities stale and produce a non-uniform solution distribution. Improvements for Constraint Solving in the SCV Library
[7] The SCV library uses the CUDD package as its BDD implementation. Improvements for Constraint Solving in the SCV Library
[8] Bit operators such as bitwise and, or, not, bit-select, and slice-select were added to scv_expression and mapped to BDD synthesis operations like BDD-AND for each bit of the operand vectors. Improvements for Constraint Solving in the SCV Library