小特集 12. 部分グラフ列挙アルゴリズムの最先端

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 12.

部分グラフ列挙アルゴリズムの最先端

The Current Situation of Subgraph Enumeration Algorithms

和佐州洋

和佐州洋 正員 国立情報学研究所情報学プリンシプル研究系

Kunihiro WASA, Member (Principles of Informatics Research Division, National Institute of Informatics, Tokyo, 101-8430 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.293-296 2018年3月

©電子情報通信学会2018

abstract

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

キーワード:離散アルゴリズム,列挙アルゴリズム,計算困難性,分割法,逆探索法

1.は じ め に

 計算機性能の向上に伴い,複雑な構造を持ったデータを大量に保有することが可能となった.それに伴い,これまで,有用な知識を発見するために多くの技法が開発されてきた.部分構造を用いた構造データの機械学習(1)や,生命情報学における遺伝子制御ネットワークや食物網の解析(2),クリーク検出によるネットワーク解析(3)などがその一例である.本稿では,これらを支える基盤的技術の一つである部分グラフ列挙アルゴリズムに着目する.列挙アルゴリズムは,次に与える問題を解くアルゴリズムである:

[問題1(部分グラフ列挙問題)] グラフmathと制約mathが与えられたときに,mathを満たすmath中の部分グラフ全てを漏れなく重複なく出力せよ.

 列挙問題としては,ほかに,実行可能解の総数を求める問題や2分決定図(BDD)(4)のように実行可能解を索引可能な構造に圧縮して出力する問題等があるが,本稿では扱わない(注1).以下では,部分グラフ列挙問題を単に列挙問題と呼ぶ.

 列挙問題に関する研究は,1950年代後半から連綿と続いてきた.その対象は,全域木や,パス,サイクル,クリーク,マッチング,カットなど多岐にわたる(網羅的なリストは文献(5)).本稿では,列挙アルゴリズムに共通する時間計算量の評価方法と列挙問題の困難性(2.),並びに,現在頻繁に用いられる技法(3.)について,その現状を述べる.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。