Title :
Improving the variable ordering of OBDDs is NP-complete
Author :
Bollig, Beate ; Wegener, Lngo
Author_Institution :
Fachbereich Inf. II, Dortmund Univ., Germany
fDate :
9/1/1996 12:00:00 AM
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
Keywords :
Boolean functions; computational complexity; decidability; diagrams; directed graphs; heuristic programming; search problems; simulated annealing; Boolean functions; NP-complete problem; heuristic algorithms; local search algorithm; ordered binary decision diagrams; simulated annealing algorithm; variable ordering; Algorithm design and analysis; Boolean functions; Circuit synthesis; Circuit testing; Computational modeling; Data structures; Heuristic algorithms; Pattern analysis; Simulated annealing; Test pattern generators;
Journal_Title :
Computers, IEEE Transactions on
