16:30 〜 16:50
[2N5-OS-17b-03] グラフの全点対間の点カットを索引化する BDD の構築
キーワード:決定グラフ、列挙、グラフアルゴリズム
与えられたグラフの点カットとして,どのような頂点集合が存在しているかを考えることは基本的である。本稿では,入力として無向グラフが与えられたとき,その全ての点対間の点カット全てを,後に利用しやすい形で索引化するためのアルゴリズムを提案する。提案アルゴリズムは,まず点カットの索引化を動的計画法の問題として定式化する。そして,その索引化に BDD と呼ばれるデータ構造を用いることで,効率的なアルゴリズムを目指す。実験では提案アルゴリズムを,規則的な構造を持つグラフである正方格子グラフ,およびランダムに生成したグラフに対して適用した。その結果,提案アルゴリズムは特に,規則的な構造を持つグラフや辺が密なグラフにおいて高速に動作することが分かった。また提案アルゴリズムの細部を少し変えることで,ベイジアンネットワークにおける d-分離を引き起こす頂点集合などの,点カットに類似した頂点集合を索引化できることを示す。
講演PDFパスワード認証
論文PDFの閲覧にはログインが必要です。参加登録者の方は「参加者用ログイン」画面からログインしてください。あるいは論文PDF閲覧用のパスワードを以下にご入力ください。