| Item type |
SIG Technical Reports(1) |
| 公開日 |
2016-11-17 |
| タイトル |
|
|
タイトル |
分枝限定法による最大辺重みクリーク抽出法 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A branch-and-bound algorithm for the maximum edge-weight clique problem |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
神戸大学大学院工学研究科 |
| 著者所属 |
|
|
|
神戸大学大学院工学研究科 |
| 著者所属 |
|
|
|
神戸大学大学院工学研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Kobe University |
| 著者所属(英) |
|
|
|
en |
|
|
Kobe University |
| 著者所属(英) |
|
|
|
en |
|
|
Kobe University |
| 著者名 |
清水, 悟司
山口, 一章
増田, 澄男
|
| 著者名(英) |
Satoshi, Shimizu
Kazuaki, Yamaguchi
Sumio, Masuda
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
辺に重みが付与された無向グラフが与えられたとき，辺の重みの和が最大のクリークを求める問題を最大辺重みクリーク問題という．最大辺重みクリーク問題は NP 困難である．従来，最大辺重みクリーク問題に対し，0 - 1 整数計画問題や二次計画問題へと定式化を行い，数理計画ソルバを用いて厳密解を求めるアプローチが研究されてきた．本稿では，分枝限定法に基づく最大辺重みクリーク問題の厳密解法を提案する．提案法は従来の方法に比べ，非常に短い計算時間で厳密解が得られることを計算機実験により確認した． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Given an edge-weighted undirected graph, to find the clique of maximum edge-weight sum is called the maximum edge weight clique problem (MEWCP). The MEWCP is NP-hard. Previous studies formulate the MEWCP as the 0 - 1 integer programming or the quadratic programming. And they use mathematical programming solvers to obtain exact solutions. In this paper, we propose an exact algorithm based on branch-and-bound for MEWCP. By some numerical experiments, we confirm our proposal algorithm is greatly faster than previous methods. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2016-AL-160,
号 11,
p. 1-6,
発行日 2016-11-17
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL16160011.pdf (632.0 kB)
