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

pp293
和佐州洋

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