[2N5-OS-17b] AIと制約プログラミング (2)

[2N5-OS-17b-03] グラフの全点対間の点カットを索引化する BDD の構築

〇髙橋 昌大¹、川原 純¹、湊 真一¹ (1. 京都大学 大学院情報学研究科)

キーワード：決定グラフ、列挙、グラフアルゴリズム

与えられたグラフの点カットとして，どのような頂点集合が存在しているかを考えることは基本的である。本稿では，入力として無向グラフが与えられたとき，その全ての点対間の点カット全てを，後に利用しやすい形で索引化するためのアルゴリズムを提案する。提案アルゴリズムは，まず点カットの索引化を動的計画法の問題として定式化する。そして，その索引化に BDD と呼ばれるデータ構造を用いることで，効率的なアルゴリズムを目指す。実験では提案アルゴリズムを，規則的な構造を持つグラフである正方格子グラフ，およびランダムに生成したグラフに対して適用した。その結果，提案アルゴリズムは特に，規則的な構造を持つグラフや辺が密なグラフにおいて高速に動作することが分かった。また提案アルゴリズムの細部を少し変えることで，ベイジアンネットワークにおける d-分離を引き起こす頂点集合などの，点カットに類似した頂点集合を索引化できることを示す。