| 講演抄録／キーワード |
| 講演名 |
2004-10-14 11:30
Approximation algorithms for the bipartite dense subgraph problem
○Akiko Suzuki・Takeshi Tokuyama（Tohoku Univ.） |
| 抄録 |
（和） |
二部グラフの高濃度部分グラフ問題と、そのデータマイニングにおける次元制限クラスタリングへの応用を論じる。過去の研究と異なり、出力される部分グラフが小さい場合にも良い理論的近似アルゴリズムを与える。 |
| （英） |
We consider the (weighted) bipartite dense subgraph problem that extracts a dense subgraph of a given (weighted) bipartite graph. We give approximation algorithms with theoretical error bounds even if the output subgraph is of small size provided that it is dense: This is significantly different from known results on the non-bipartite problem. We also discuss its application to dimension-reducing clustering in data mining applications. |
| キーワード |
（和） |
近似アルゴリズム / クラスタリング / 高濃度部分グラフ / / / / / |
| （英） |
Approximation Algorithm / Clustering / Dense subgraph / / / / / |
| 文献情報 |
信学技報, vol. 104, no. 338, COMP2004-37, pp. 17-24, 2004年10月. |
| 資料番号 |
COMP2004-37 |
| 発行日 |
2004-10-07 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|