Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams

1 January 1991

proceedings article
Published by Association for Computing Machinery (ACM)

p. 417-420
https://doi.org/10.1145/127601.127705

Abstract

Variable ordering is critical in the efficient representation of functions as Ordered Binary Decision Diagrams (OBDDS). In this paper we present new heuristics to determine “good” variable orderings. We use a new representation form, Ordered Partial Decision Diagrams (OPDDs)~ to evaluate heuristically generated orders on large crccuits. Several improved orders are located for benchmark circuits, and an overall ordering strategy is introduced which includes partial functional calculations and which requires insignificant computation resources.

Keywords

BINARY DECISION DIAGRAM
VARIABLE ORDERING
EFFICIENT MANIPULATION
BOOLEAN FUNCTIONS
DECISION DIAGRAM
DISTRIBUTED COMPUTING
CIRCUITS
DATA STRUCTURES
COMPUTATIONAL COMPLEXITY

This publication has 0 references indexed in Scilit: