文献

J-GLOBAL ID：201402220308056980   整理番号：14A1464296

「フカシギの数え方」から広がるアルゴリズムの理工学-二分決定グラフによる離散構造処理と広がる応用分野-1.二分決定グラフによる離散構造処理の概観

著者 (1件)： 湊真一 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会誌  (Journal of the Institute of Electronics, Information and Communication Engineers)
巻： 97  号： 12  ページ： 1074-1079  発行年： 2014年12月01日 
JST資料番号： F0019A  ISSN： 0913-5693  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 論理関数や集合などの基本的な離散構造データを効率良く演算処理することは,様々な応用分野に共通する基盤技術として非常に重要である。本稿ではBDD(Binary Decision Diagram,二分決定グラフ)及びZDD(Zero-suppressed BDD,ゼロサプレス型BDD)を用いた離散構造データの処理技法を概観する。まずBDDによるブール演算処理,ZDDによる組合せ集合の代数処理について述べ,次に文字列集合や順列集合への発展について述べる。更に最近注目されているグラフ列挙の手法や,その適用例である「おねえさんの問題」など,本研究分野における最近の展開について紹介する。(著者抄録)

シソーラス用語： *データ処理 ,  *離散系 ,  構造 ,  *二分決定グラフ ,  Boole関数
準シソーラス用語： *ゼロサプレス二分決定グラフ ,  *離散構造

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

引用文献 (22件)：

• R.E. Bryant, “Graph-based algorithms for Boolean function manipulation,“ IEEE Trans. Comput., vol. C-35, no. 8, pp. 677-691, 1986.
• 藤田昌宏,佐藤政生,“BDD(二分決定グラフ),“情報処理,vol.34,no.5,pp.584-630,1993.
• S. Minato, Binary decision diagrams and applications for VLSI CAD, Kluwer Academic Publishers, 1996.
• S. Minato, “Zero-suppressed BDDs for set manipulation in combinatorial problems,“ Proc. of 30th ACM/IEEE Design Automation Conference (DAC '93), pp. 272-277, 1993.
• D.E. Knuth, The Art of Computer Programming : Bitwise Tricks & Techniques ; Binary Decision Diagrams, vol. 4, fascicle 1, Addison-Wesley, 2009.

タイトルに関連する用語 (6件)： フカ ,  シギ ,  アルゴリズム ,  二分決定グラフ ,  離散構造 ,  応用