ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 研究報告
  2. 数理モデル化と問題解決(MPS)
  3. 2021
  4. 2021-MPS-134

An Improved Branch-and-Bound MCT Algorithm for Finding a Maximum Clique

https://ipsj.ixsq.nii.ac.jp/records/212162
https://ipsj.ixsq.nii.ac.jp/records/212162
1b86a7d3-2060-4a71-b5fc-525bebe3ba95
名前 / ファイル ライセンス アクション
IPSJ-MPS21134003.pdf IPSJ-MPS21134003.pdf (644.6 kB)
Copyright (c) 2021 by the Information Processing Society of Japan
オープンアクセス
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

× Etsuji, Tomita

Etsuji, Tomita

Search repository
Jiro, Yanagisawa

× Jiro, Yanagisawa

Jiro, Yanagisawa

Search repository
Kengo, Katayama

× Kengo, Katayama

Kengo, Katayama

Search repository
Kazuho, Kanahara

× Kazuho, Kanahara

Kazuho, Kanahara

Search repository
Takahisa, Toda

× Takahisa, Toda

Takahisa, Toda

Search repository
Hiro, Ito

× Hiro, Ito

Hiro, Ito

Search repository
Mitsuo, Wakatsuki

× Mitsuo, Wakatsuki

Mitsuo, Wakatsuki

Search repository
Tetsuro, Nishino

× Tetsuro, Nishino

Tetsuro, Nishino

Search repository
著者名(英) Etsuji, Tomita

× Etsuji, Tomita

en Etsuji, Tomita

Search repository
Jiro, Yanagisawa

× Jiro, Yanagisawa

en Jiro, Yanagisawa

Search repository
Kengo, Katayama

× Kengo, Katayama

en Kengo, Katayama

Search repository
Kazuho, Kanahara

× Kazuho, Kanahara

en Kazuho, Kanahara

Search repository
Takahisa, Toda

× Takahisa, Toda

en Takahisa, Toda

Search repository
Hiro, Ito

× Hiro, Ito

en Hiro, Ito

Search repository
Mitsuo, Wakatsuki

× Mitsuo, Wakatsuki

en Mitsuo, Wakatsuki

Search repository
Tetsuro, Nishino

× Tetsuro, Nishino

en Tetsuro, Nishino

Search repository
論文抄録
内容記述タイプ 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
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-19 17:34:57.926274
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3