IEICE Trans - The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram

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.