articleTop 1% cited
Improving the variable ordering of OBDDs is NP-complete
IEEE Transactions on Computers · 1996 · Vol. 45(9) · pp. 993–1002
Beate Bollig✉(TU Dortmund University)Ingo Wegener(TU Dortmund University)
Abstract
Ordered binary decision diagrams are a useful representation of Boolean functions, if a good variable ordering is known. Variable orderings are computed by heuristic algorithms and then improved with local search and simulated annealing algorithms. This approach is based on the conjecture that the following problem is NP-complete. Given an OBDD G representing f and a size bound s, does there exist an OBDD G* (respecting an arbitrary variable ordering) representing f with at most s nodes? This conjecture is proved.
Formal Methods in VerificationVLSI and Analog Circuit Testingsemigroups and automata theoryBinary decision diagramBoolean functionSimulated annealingConjectureVariable (mathematics)MathematicsCombinatoricsHeuristicDiscrete mathematicsBinary number
Funding
- Deutsche Forschungsgemeinschaft
Citations
547
FWCI
21.16
field-weighted impact
References
24
Percentile
100%
vs. same field & year
Citations per year
References
Symbolic Boolean manipulation with ordered binary-decision diagrams
ACM Computing Surveys · 1992 · 1,999 citations
Graph-Based Algorithms for Boolean Function Manipulation
IEEE Transactions on Computers · 1986 · 8,843 citations
Citation Network
How this paper connects to the literature. Drag to explore, click any node to open that paper.