| Item type |
SIG Technical Reports(1) |
| 公開日 |
2021-07-20 |
| タイトル |
|
|
タイトル |
An Improved Branch-and-Bound MCT Algorithm for Finding a Maximum Clique |
| タイトル |
|
|
言語 |
en |
|
タイトル |
An Improved Branch-and-Bound MCT Algorithm for Finding a Maximum Clique |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
The University of Electro-Communications |
| 著者所属 |
|
|
|
East Nippon Expressway Co. Ltd. |
| 著者所属 |
|
|
|
Okayama University of Science |
| 著者所属 |
|
|
|
Okayama University of Science |
| 著者所属 |
|
|
|
The University of Electro-Communications |
| 著者所属 |
|
|
|
The University of Electro-Communications／CREST |
| 著者所属 |
|
|
|
The University of Electro-Communications |
| 著者所属 |
|
|
|
The University of Electro-Communications |
| 著者所属(英) |
|
|
|
en |
|
|
The University of Electro-Communications |
| 著者所属(英) |
|
|
|
en |
|
|
East Nippon Expressway Co. Ltd. |
| 著者所属(英) |
|
|
|
en |
|
|
Okayama University of Science |
| 著者所属(英) |
|
|
|
en |
|
|
Okayama University of Science |
| 著者所属(英) |
|
|
|
en |
|
|
The University of Electro-Communications |
| 著者所属(英) |
|
|
|
en |
|
|
The University of Electro-Communications / CREST |
| 著者所属(英) |
|
|
|
en |
|
|
The University of Electro-Communications |
| 著者所属(英) |
|
|
|
en |
|
|
The University of Electro-Communications |
| 著者名 |
Etsuji, Tomita
Jiro, Yanagisawa
Kengo, Katayama
Kazuho, Kanahara
Takahisa, Toda
Hiro, Ito
Mitsuo, Wakatsuki
Tetsuro, Nishino
|
| 著者名(英) |
Etsuji, Tomita
Jiro, Yanagisawa
Kengo, Katayama
Kazuho, Kanahara
Takahisa, Toda
Hiro, Ito
Mitsuo, Wakatsuki
Tetsuro, Nishino
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
We improve a branch-and-bound algorithm called MCT（Tomita et al., FAW 2016, LNCS 9711, pp.215-226, 2016) for finding a maximum clique. First, we devise a new efficient approximation algorithm for finding a maximum clique. Second, we employ MIS vertex ordering with an appropriate precondition. Third, we employ a combination of Re-NUMBER and Infra-chromatic bound. Finally, we devise an adaptive change of stages of the search tree. The finally improved MCT algorithm is named MCT*. It is shown that MCT* algorithm is significantly faster than MCT by extensive computational experiments. In addition, it is shown that MCT* algorithm is faster than the state-of-the-art IncMC2 algorithm（Li et al., INFORMS J. Computing, 30, pp. 137-153, 2018）for many instances. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
We improve a branch-and-bound algorithm called MCT（Tomita et al., FAW 2016, LNCS 9711, pp.215-226, 2016) for finding a maximum clique. First, we devise a new efficient approximation algorithm for finding a maximum clique. Second, we employ MIS vertex ordering with an appropriate precondition. Third, we employ a combination of Re-NUMBER and Infra-chromatic bound. Finally, we devise an adaptive change of stages of the search tree. The finally improved MCT algorithm is named MCT*. It is shown that MCT* algorithm is significantly faster than MCT by extensive computational experiments. In addition, it is shown that MCT* algorithm is faster than the state-of-the-art IncMC2 algorithm（Li et al., INFORMS J. Computing, 30, pp. 137-153, 2018）for many instances. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN10505667 |
| 書誌情報 |
研究報告数理モデル化と問題解決（MPS）
巻 2021-MPS-134,
号 3,
p. 1-4,
発行日 2021-07-20
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8833 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-MPS21134003.pdf (644.6 kB)
