|
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
|
The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
Seiichiro TANI Kiyoharu HAMAGUCHI Shuzo YAJIMA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E79-D
No.4
pp.271-281 Publication Date: 1996/04/25 Online ISSN:
DOI: Print ISSN: 0916-8532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: ordered binary decision diagram, variable ordering, optimal linear arrangement, NP-complete, Boolean function,
Full Text: PDF>>
Summary:
An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.
|
|
|