文献

J-GLOBAL ID：201302238247125737   整理番号：13A1077285

写像枝を用いた系列二分決定グラフの効率化

An Efficient Sequence Binary Decision Diagrams with Mapping Edges

著者 (4件)： 青木洋士 (北大) ,  湊真一 (北大) ,  湊真一 (JST-ERATO) ,  山下茂 (立命館大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 50(COMP2013 9-18)  ページ： 149-156  発行年： 2013年05月10日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 二分決定グラフ(Binary Decision Diagram,BDD)は,論理関数を効率良く処理することができるグラフである。BDD処理系のメモリ効率は,節点数に依存する。BDDの節点数を削減する手法として,BDDに属性枝を付与する手法が提案されている。BDDに属性枝を付与すると,同じ部分グラフの数が増加し,同一の節点が効率良く共有される。一方,系列二分決定グラフ(Sequence Binary Decision Diagram,SeqBDD)は,文字列集合を表現するデータ構造である。SeqBDDは,変数の出現順序や構築ルールがBDDと異なる。このため,SeqBDDは,BDDとは違った節点の共有手法を適用できる可能性がある。本稿では,属性枝を付与した新しいSeqBDDの節点の共有手法を提案する。実験により,SeqBDDに対して提案した属性枝の手法を適用すると,節点数を削減することができ,さらに,特定のSeqBDDの演算を高速化できることを確認した。(著者抄録)

シソーラス用語： *二分決定グラフ ,  *論理関数 ,  記憶容量 ,  文字列 ,  節点 ,  評価試験 ,  高速化 ,  グラフ理論 ,  計算機アルゴリズム ,  *配置問題 ,  *地理情報システム ,  地図 ,  最大化問題 ,  *NP困難 ,  回転 ,  ラベル付け【画像】 ,  点
準シソーラス用語： BDD【グラフ】 ,  アンカー点 ,  欲張りアルゴリズム

分類 (5件)： グラフ理論基礎  (IA02020S) ,  論理代数  (JB03000H) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  その他の情報処理  (JE15050M) ,  計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 写像 ,  枝 ,  系列 ,  二分決定グラフ ,  効率化