WEKO3
アイテム
最大クリーク抽出のより高速な分枝限定アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/31723
https://ipsj.ixsq.nii.ac.jp/records/317231639faac-47c6-4739-a7c0-ccac183bd779
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL06108011.pdf (306.1 kB)
|
Copyright (c) 2006 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2006-09-27 | |||||||
| タイトル | ||||||||
| タイトル | 最大クリーク抽出のより高速な分枝限定アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Faster Branch-and-Bound Algorithm for Finding a Maximum Clique | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 電気通信大学大学院電気通信学研究科情報通信工学専攻 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学電気通信学部情報通信工学科 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学電気通信学部情報通信工学科 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学電気通信学部情報通信工学科 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学大学院電気通信学研究科情報通信工学専攻 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Electro-Communications, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Communication Engineering, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Communication Engineering, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Communication Engineering, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Electro-Communications, The University of Electro-Communications | ||||||||
| 著者名 |
須谷洋一
× 須谷洋一
|
|||||||
| 著者名(英) |
Yoichi, Sutani
× Yoichi, Sutani
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 無向グラフから最大クリークを1つ抽出する問題はグラフ理論における基本的な問題であり 多くの数理問題に応用できることから重要である. これまで筆者らは 逐次的な近似彩色を用いた分枝限定法による効率の良い最大クリーク抽出アルゴリズムを発表してきた. 本稿では それらのアルゴリズムにさらに幾つかの新たな効率化手法を組み合わせることにより 多くの問題に対してより高速に解を得ることのできる最大クリーク抽出アルゴリズムを提唱する． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Finding a maximum clique is a basic problem in the graph theory, and many practical problems can be formulated as this problem. We have shown efficient branch-and-bound algorithms for finding a maximum clique using an approximate coloring. In this article, we present a faster algorithm which employes an improved approximate coloring and other techniques. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 2006, 号 100(2006-AL-108), p. 79-86, 発行日 2006-09-27 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
