| Item type |
SIG Technical Reports(1) |
| 公開日 |
2018-09-18 |
| タイトル |
|
|
タイトル |
最大クリーク抽出アルゴリズムMCTの高速化 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
An Improved MCT Algorithm for Finding a Maximum Clique |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
電気通信大学情報理工学研究科 |
| 著者所属 |
|
|
|
電気通信大学先進アルゴリズム研究ステーション |
| 著者所属 |
|
|
|
お茶の水女子大学基幹研究院／JST CREST |
| 著者所属 |
|
|
|
電気通信大学情報理工学研究科／JST CREST |
| 著者所属 |
|
|
|
電気通信大学情報理工学研究科／電気通信大学先進アルゴリズム研究ステーション |
| 著者所属 |
|
|
|
電気通信大学情報理工学研究科／電気通信大学先進アルゴリズム研究ステーション |
| 著者名 |
松崎, 空良
富田, 悦次
長尾, 篤樹
伊藤, 大雄
若月, 光夫
西野, 哲朗
|
| 著者名(英) |
Sora, Matsuzaki
Etsuji, Tomita
Atsuki, Nagao
Hiro, Ito
Mitsuo, Wakatsuki
Tetsuro, Nishino
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
筆者らが以前に提唱した最大クリーク抽出アルゴリズム MCT （FAW 2016，LNCS 9711，pp．215-226，2016） の高速化を行った．このために，最大クリーク抽出の厳密解アルゴリズムの前処理として既に有効性が確認されている最大クリーク近似解抽出アルゴリズムの改良を行い，それに加えて，効果的な分枝限定を可能にする節点の順序と従来の節点の順序を適切に切り替える処理を導入した．本提唱最大クリーク抽出アルゴリズムは，Chu-Min Li らの提案した最新アルゴリズム IncMC2 （INFORMS J．Computing，30，pp．137-153，2018） との比較実験により，多くの問題について IncMC2 他のアルゴリズムより高速であることを示した． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN10505667 |
| 書誌情報 |
研究報告数理モデル化と問題解決（MPS）
巻 2018-MPS-120,
号 21,
p. 1-6,
発行日 2018-09-18
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8833 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-MPS18120021.pdf (861.4 kB)
