共有二分決定グラフの「幅」に着目した変数順序づけ手法
スポンサーリンク
概要
- 論文の詳細を見る
論理関数の表現法として、Bryantが提案した二分決定グラフ(BDD: Binary Decision Diagrams)、および、これを発展させた共有二分決定グラフ(SBDD: Shared BDD)は、検証、テスト生成、論理合成などの処理に対して非常に有効であり、最近盛んに用いられている。共有二分決定グラフ(以下、単にBDDと呼ぶ)は、入力変数の順序によってグラフのサイズが著しく変化することが多いため、いかにして順序づけを行うかということが、実用上極めて重要な問題となっている。本稿では、あるBDDを与えられたときに、BDDの「幅」と呼ぶ値に着目して変数順序を再配置する手法を提案する。実験によれば、多くの場合、相当によい解を与えるという結果を得た。
- 一般社団法人情報処理学会の論文
- 1991-02-25
著者
-
湊 真一
Ntt Lsi研究所
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
湊 真一
Ntt Lsi 研究所
関連論文
- Flexcastによる段階的導入に優れたマルチキャストシステムの設計と実装(ネットワーク・並列分散システムソフトウェア, システム開発論文)
- Flexcastに基づくマルチキャストシステムの開発とその方式設計について(映像通信,コンテンツ配信ネットワーク,マルチキャスト,一般)
- Flexcastによるインターマルチキャスティング方式の提案と日米映像配信実験(映像通信, コンテンツ配信ネットワーク, マルチキャスト, 一般)
- JGNを介した大規模映像配信プラットフォーム(新しいトラヒックモデルと性能評価及び一般)
- B-7-66 リアルタイムストリーム配信における FEC 適用時の課題に関する一考察
- B-7-47 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (3) 日米間超長距離ネットワークにおける実証実験
- B-7-46 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (2) 動的アドレスマッピングによるオンデマンド IP マルチキャストトンネリング
- B-7-45 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (1) Flexcast と IP マルチキャストの連携方式
- BS-5-5 漏洩者の特定と配信停止が可能なマルチキャスト配信方式(BS-5. ネットワークサービスのセキュリティ技術の展開,シンポジウムセッション)
- B-7-4 ネットワークによるフロー切り替えを行うマルチキャスト電子透かし方式の検討(B-7.情報ネットワーク,一般講演)
- B-7-31 トラヒックの平滑化とFECによる講義ノート映像品質の改善(B-7.情報ネットワーク, 通信2)
- Flexcastを用いた講義ノート多地点同報配信システムの検討(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- FlexcastとJavaAppletに基づくプログラマブルな多地点同報配信アプリケーションの実装法(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- B-7-73 MulticastVNCを用いた講義ノート配信システムのトラヒック特性評価(B-7. 情報ネットワーク, 通信2)
- 論理合成技術
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDD(二分決定グラフ)とその応用
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム (デザインガイア'99--システム設計とCAD技術及び一般)
- ゼロサプレス型BDDを用いた系列長制限つき正規表現処理方法
- 48. 道南における胸部 X 線撮影の現況 : 第 4 報 X 線管焦点について(X 線撮影 II, 北海道部会)
- ベイジアンネットワークと離散構造処理系(ベイジアンネットワークの最先端)
- 5.メディア系異分野共同研究プロジェクト(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- D-4-18 高速ストリーム処理のための文字列パターン照合手法とそのFPGA設計(D-4. データ工学,一般セッション)
- D-1-7 並列ビット分配にもとづいた効率的な正規表現照合アルゴリズム(D-1.コンピュテーション,一般セッション)
- BDD/ZDDを用いたペントミノパズルの解の列挙
- 非巡回正規表現に対する効率的なパターン照合
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- 命題論理に基づく確率モデルのための二部決定グラフと順序符号化を用いた効率的なEMアルゴリズム(一般講演(構造学習・ベイジアンネット・確率推論),機械学習とその応用)
- 6ZK-10 二分決定グラフを用いた数独パズルの解探索と列挙(情報爆発時代におけるストリームデータと実世界情報処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- Double-Decker RFID Tags--Basic Structures and Applications (日韓合同ワークショップ 1st Korea-Japan Joint Workshop on Ubiquitous Computing and Networking Systems (ubiCNS 2005))
- 3ZP-5 ZDDを用いた立体ペントミノパズルの解の列挙(情報爆発時代におけるデータマイニング・アルゴリズム,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 二分モーメントグラフを用いた大規模多項式の操作手法
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- BDDの規模によらず一定の実記憶の範囲内で動作するストリーム形式BDD処理アルゴリズム
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 18. 道南における胸部X線撮影の現況 第2報 : 装置の施設間比較 : 北海道部会 : その他
- B-7-108 Virtual BUSにおける資源管理探索機構
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法(データマイニング,データ工学論文)
- 座長集約 核医学(29〜34)(北海道部会)
- F-024 ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成とその評価(F分野:人工知能・ゲーム,一般論文)
- 頻出パターンマイニングのためのゼロサプレス型BDDの変数順序付け方法とその評価(データマイニング,データ工学論文)
- F-011 頻出パタンマイニングのためのゼロサプレス型BDDの変数順序付け方法の高速化の検討(F分野:人工知能・ゲーム)
- F_019 データベース解析のためのゼロサプレス型二分決定グラフの簡単化について(F分野:人工知能・ゲーム)
- データベース解析のためのゼロサプレス型二分決定グラフの簡単化に関する考察 (テーマ:特集「ウェブデータの知的処理」および一般)
- ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成 (特集 「知識発見の生命科学への応用」および一般)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- F-013 ゼロサプレス型BDDを用いた無順序n-gram表現法の性能評価(F分野:人工知能・ゲーム)
- F-020 コルモゴロフ複雑性に基づく画像圧縮と分類に関する実験と考察(人工知能・ゲーム,一般論文)
- F-012 頻出パタン集合を表現する二分決定グラフの変数順序改善法に関する実験と考察(F分野:人工知能・ゲーム)
- ゼロサプレスBDDによるペトリネットのCTL記号モデル検査
- D-009 ZDDを用いた頻出パタン演算によるWebテキストデータからの知識発見とその評価(D分野:データベース,一般論文)
- F-061 ベイジアンネットワークを表現するZDDの初期変数順序付け方法の改良(人工知能・ゲーム,一般論文)
- D-031 頻出パタン抽出アルゴリズム「LCM over ZDDs」の変数順序付けの影響に関する考察(データベース,一般論文)
- F-050 ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付けに関する実験と考察(人工知能・ゲーム,一般論文)
- ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 二分決定グラフ(BDD)による命題論理プログラミング
- Symmetric item set mining method using zero-suppressed BDDs and application to biological data (論文特集:データマイニングと統計数理)
- 算術論理式システムBEM-2を使ってパズルを解こう
- ZDDによるベイジアンネットワーク推論の高速化 (特集 「ベイジアン・ネットワークと応用」および一般)
- ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付け方法に関する考察 (特集 「ベイジアン・ネットワークと応用」および一般)
- Manipulation of Large-Scale Polynomials Using BMDs (Special Section on VLSI Design and CAD Algorithms)
- アルゴリズム記述からのBDD生成
- 組合せ回路検証の技術
- 二分決定グラフによる制約充足問題の解法
- ゼロサプレス型BDDを用いた非明示的積和形表現の高速因数分解法
- 2. 計算機上での BDD の処理技法 (<特集> BDD (二分決定グラフ))
- 「わくわく」 - 技術革新のキーワード -
- 共有二分決定グラフの「幅」に着目した変数順序づけ手法
- 論理関数の共有二分決定グラフによる表現とその効率的処理手法
- 共有二分決定図を用いた論理関数の処理手法について
- 真理値表表現を用いた記号シミュレータ
- AI-1-5 大規模な離散構造データを扱うためのGPU利用法の検討(AI-1.GPUを用いた高速化技術とそのVLSI設計への応用,依頼シンポジウム,ソサイエティ企画)
- BS-1-2 順列集合を操作する効率的なデータ構造とアルゴリズムの研究について(BS-1. 学生による研究室交流会,シンポジウムセッション)
- 写像枝を用いた系列二分決定グラフ (Theoretical Foundations of Computing)
- 組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化 (Theoretical Foundations of Computing)
- 系列二分決定グラフを操作するための豊富な演算体系の構築 (Theoretical Foundations of Computing)
- ベイジアンネットワークとZDDに関する最近の研究状況について (特集 「ベイジアンネットワークとその応用」および一般)
- 招待講演 フロンティア法 : BDD/ZDDを用いた高速なグラフ列挙索引化の技法 (情報ネットワーク)
- 最先端の開拓者たち 湊真一氏 北海道大学大学院 情報科学研究科 教授 世界的権威が認めた超高速アルゴリズム 電力危機に挑む
- 5.ZDDを用いた新たな列挙手法(広がる列挙の技術-列挙による問題解決アプローチ-)
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- BDD/ZDDの技法と離散構造処理系(離散構造処理系-知能情報処理を支えるアルゴリズムの技法)
- DK-2-2 フロンティア法の種々のリンクパズル問題への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-1 フロンティア法 : ZDDを用いた極めて高速なグラフ列挙索引化アルゴリズム(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-2 フロンティア法の種々のリンクパズル問題への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-1 フロンティア法 : ZDDを用いた極めて高速なグラフ列挙索引化アルゴリズム(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DS-1-13 πDDのConjugacy Class計算への適用とその性能評価(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- Counterexamples to the long-standing conjecture on the complexity of BDD binary operations
- DS-1-14 πDDの順列集合演算を用いたパンケーキ整列問題の解析法(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- グラフ列挙索引化技法の種々の問題への適用 (特集 BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- BDD/ZDDを用いたグラフ列挙索引化技法 (特集 BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- 順列二分決定グラフを用いたパターン回避順列の列挙索引化
- 最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ