小特集　グラフアルゴリズムの最先端 12. 部分グラフ列挙アルゴリズムの最先端 The Current Situation of Subgraph Enumeration Algorithms

和佐州洋

膨大かつ複雑なデータから有用な情報を抽出
　グラフで記述された複雑なデータから有用な情報を抽出する重要性が，SNSや生命科学など分野を問わずに増している．列挙アルゴリズム，すなわち，与えられたデータから，制約を満たす部分構造を全て出力するアルゴリズムは，このような要請を実現するための基盤技術の一つである．本稿では，列挙アルゴリズムに関する評価方法，困難性の判定，及び，代表的な技法について，現在の状況を解説する．