[4K1-OS-16a] AI における離散構造処理と制約充足(1)

[4K1-OS-16a-05] 有向ハイパーグラフ上での到達可能性判定の高速化

〇佐々木 耀一¹、木村 圭吾¹、山本 風人¹、岡嶋 穣¹、定政 邦彦¹ (1. NEC セキュリティ研究所)

キーワード：有向ハイパーグラフ、ZDD、到達可能性判定問題

本論文では有向ハイパーグラフ(DH)上での到達可能性判定問題を高速に解くためのアルゴリズムを研究する。
DHは有向グラフとハイパーグラフそれぞれの特徴を持ち、より一般化されたグラフとみることができる。
本問題に対し、推移閉包情報の性質を活かすため組合せ集合に特化した圧縮を行うことにより，メモリ使用量を減らしつつ，高速に到達可能性判定を行うことができるアルゴリズムを提案する．