IMPROVING THE VARIABLE ORDERING OF OBDDS IS NP-COMPLETE

Authors
BOLLIG B WEGENER I
Citation
B. Bollig et I. Wegener, IMPROVING THE VARIABLE ORDERING OF OBDDS IS NP-COMPLETE, I.E.E.E. transactions on computers, 45(9), 1996, pp. 993-1002
Citations number
18
Categorie Soggetti
Computer Sciences","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
Journal title
I.E.E.E. transactions on computers → ACNP
ISSN journal
00189340
Volume
45
Issue
9
Year of publication
1996
Pages
993 - 1002
Database
ISI
SICI code
0018-9340(1996)45:9<993:ITVOOO>2.0.ZU;2-I
Abstract
Ordered binary decision diagrams are a useful representation of Boolea n functions, ii a good variable ordering is known. Variable orderings are computed by heuristic algorithms and then improved with local sear ch and simulated annealing algorithms. This approach is based on the c onjecture that the following problem is NP-complete. Given an OBDD G r epresenting f and a size bound s, does there exist an OBDD G (respect ing an arbitrary variable ordering) representing with at most s nodes? This conjecture is proved.