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

• TANI Seiichiro

  Department of Information Science, The University of Tokyo

• HAMAGUCHI Kiyoharu

  Department of Information Science, Kyoto University

• YAJIMA Shuzo

  Department of Information Science, Kyoto University

抄録

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.

収録刊行物

• IEICE transactions on information and systems

  IEICE transactions on information and systems 79 (4), 271-281, 1996-04-25

  一般社団法人電子情報通信学会

キーワード

• ordered binary decision diagram
• variable ordering
• optimal linear arrangement
• NP-complete
• Boolean function

詳細情報

• CRID: 1573105977193445888
• NII論文ID: 110003209644
• NII書誌ID: AA10826272
• ISSN: 09168532
• 本文言語コード: en
• データソース種別:
  • CiNii Articles