二分決定グラフの最適変数順序付け問題の計算複雑さ

• Item type: SIG Technical Reports(1)
• 公開日: 1993-03-10
• タイトル: 二分決定グラフの最適変数順序付け問題の計算複雑さ
• タイトル / 言語: en
• タイトル: The Complexity of the Variable Ordering Problems of Binary Decision Diagrams
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学工学部情報工学教室
• 著者所属: 京都大学工学部情報工学教室
• 著者所属: 京都大学工学部情報工学教室
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Engineering, Kyoto University
• 著者名: 谷, 誠一郎; 濱口, 清治; 矢島, 脩三
• 著者名(英): Seiichiro, Tani; Kiyoharu, Hamaguchi; Shuzo, Yajima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 論理関数の効率的表現方法の一つである二分決定グラフの節点数は、変数の順序付けに大きな影響を受ける。本稿では、共有二分決定グラフ最適変数順序付け問題、すなわち節点数nの共有二分決定グラフSBと自然数k（<）が与えられたときSBと同じ論理関数の集合を表す節点数k以下の共有二分決定グラフを実現するような変数の順序付けが存在するかという問題について、これかNP完全であることの証明を行う。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A binary decision diagram (BDD) is used as an efficient way of the representation of a Boolean function. The size of BDD's is highly sensitive to the variable ordering. In this paper, it is proved that the optimal variable ordering problem of shared binary decision diagrams (SBDD's) (OVO) is NP-complete. The problem is to decide whether, for a given SBDD with n nodes and a positive integer k (<n), there exists a variable ordering for some graph whose nodes are less than or equal to k and which represents the same Boolean functions as are represented by the given SBDD.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1993, 号 19(1992-PRO-011), p. 139-147, 発行日 1993-03-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会