[4K1-OS-16a] [Organized Session] OS-16

[4K1-OS-16a-05] Efficient Algorithm to Reachability Problem on Directed Hypergraph

〇Yoichi Sasaki¹, Keigo Kimura¹, Kazeto Yamamoto¹, Yuzuru Okajima¹, Kunihiko Sadamasa¹ (1. Security Research Labs., NEC Corp.)

Keywords:Directed hypergraph, ZDD, Reachability problem

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