| 大会名称 |
|---|
| 2019年 総合大会 |
| 大会コ－ド |
| 2019G |
| 開催年 |
| 2019 |
| 発行日 |
| 2019-03-05 |
| セッション番号 |
| DS-1 |
| セッション名 |
| COMP 学生シンポジウム |
| 講演日 |
| 2019/03/19 |
| 講演場所(会議室等) |
| 54号館 102教室 |
| 講演番号 |
| DS-1-8 |
| タイトル |
| サイズ関数を一般化した最密部分グラフ問題 |
| 著者名 |
| 河瀬康志, ◎宮内敦史, |
| キーワード |
| グラフ, 密グラフ抽出, 最密部分グラフ問題, 近似アルゴリズム |
| 抄録 |
| 本研究では，ネットワーク解析における基本的かつ重要な操作である密グラフ抽出を扱った．密グラフ抽出に対しては，様々な最適化モデルが知られているが，そのなかで最も活発に利用されているのが，最密部分グラフ問題である．しかしながら，最密部分グラフ問題では，出力する部分グラフのサイズを指定できず，応用上望まれているサイズの部分グラフが求められない場合がある．本研究では，この問題を解決するため，最密部分グラフ問題を一般化し，新たな最適化問題を導入した．この問題に対して，多項式時間の厳密アルゴリズムや精度保証付き近似アルゴリズムを設計した． |
| 本文pdf |
|
PDF download
|