Title: The complexity of the optimal variable ordering problems of shared binary decision diagrams
Abstract: A binary decision diagram (BDD) is a directed acyclic graph for representing a Boolean function. BDD's are widely used in various areas which require Boolean function manipulation, since BDD's can represent efficiently many of practical Boolean functions and have other desirable properties. However the complexity of constructing BDD's has hardly been researched theoretically. In this paper, we prove that the optimal variable ordering problem of shared BDD's is NP-complete, and touch on the hardness of this problem and related problems of BDD's.
Publication Year: 1993
Publication Date: 1993-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 87
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot