高密度部分グラフの抽出──その計算限界と打破──

徳山　豪

あらまし

徳山　豪

Vol.92 No.2pp.82-89

発行日:2009/02/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集　特定領域研究「新世代の計算限界──その解明と打破──」

専門分野:

キーワード:
アルゴリズム, 近似困難性, インスタンス依存性, 高密度部分グラフ,

本文:PDF(587.7KB)>>

あらまし:
グラフの高密度部分の抽出はデータマイニングやインターネット解析などで必須の計算問題である．実用的に良い解法を求める様々な工夫が行われている一方で，これは計算理論的に難しい問題とされ，PCP理論と呼ばれる理論によって得られる計算限界が存在し，定式化によっては良い近似解を得ることすら困難である．しかしながら，近年では入力インスタンス特性やパラメータに依存した困難性の解析を数学的に行うことにより，幾つかの糸口が見えてきている．本稿では筆者自身の研究を中心に，それらのアプローチについて紹介する．

あらまし

ログイン

メニュー