文献

J-GLOBAL ID：201202222707161914   整理番号：12A1585541

BDD/ZDDを用いたグラフ列挙索引化技法

著者 (2件)： 湊真一 (北大) ,  湊真一 (JST-ERATO)
資料名： オペレーションズ・リサーチ
巻： 57  号： 11  ページ： 597-603  発行年： 2012年11月01日 
JST資料番号： F0251A  ISSN： 0030-3674  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,与えられたグラフ構造のなかから,ある制約条件を満たすような部分グラフ構造をすべて列挙し,それらをBDD/ZDDを用いて圧縮表現して索引化する技法について述べる。まず,BDD/ZDDとその演算処理系について簡単に説明し,次に,ZDDを用いた高速なパス列挙索引化アルゴリズムSimpathの概要を解説する。このアルゴリズムはKnuthが近年提案したものであるが,制約条件によって多くのバリエーションが存在することから,われわれはそれらを総称して「フロンティア法」と呼んでいる。本稿ではフロンティア法がなぜ高速であるか,そして従来のBDD/ZDDを用いた制約充足問題の解法との違いについて述べる。(著者抄録)

シソーラス用語： *二分決定グラフ ,  論理関数 ,  *データ構造 ,  データ圧縮 ,  部分集合 ,  制約条件 ,  *論理演算 ,  集合演算 ,  *グラフ理論 ,  索引作成 ,  *数え上げ理論 ,  *高速アルゴリズム ,  制約充足問題 ,  CPU時間 ,  組合せ問題
準シソーラス用語： BDD【グラフ】 ,  *ZDD ,  *グラフ構造 ,  計算時間

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

引用文献 (12件)：

• AKERS, S. B. Binary decision diagrams. IEEE Thansactions on Computers. 1978, C-27, 6, 509-516
• BRYANT, R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers. 1986, C-35, 8, 677-691
• COUDERT, O. Solving graph optimization problems with ZBDDs. Proc. of ACM/IEEE European Design and Test Conference (ED&TC '97). 1997, 224-228
• KNUTH, D. E. The Art of Computer Programming : Bitwise Tricks & Techniques ; Binary Decision Diagrams. 2009, 4, fascicle 1
• MINATO, S. Zero-suppressed BDDs for set manipulation in combinatorial problems. Proc. of 30th ACM/IEEE Design Automation Conference (DAC'93). 1993, 272-277

タイトルに関連する用語 (5件)： BDD ,  ZDD ,  グラフ ,  索引 ,  技法