WEKO3
アイテム
グラフスペクトルによる多項式時間最大クリーク抽出
https://ipsj.ixsq.nii.ac.jp/records/207925
https://ipsj.ixsq.nii.ac.jp/records/20792529e86e89-d6fe-4c54-a714-cd78fdb1043b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL20180023.pdf (858.2 kB)
|
Copyright (c) 2020 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2020-11-18 | |||||||
| タイトル | ||||||||
| タイトル | グラフスペクトルによる多項式時間最大クリーク抽出 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Polynomial-time Extraction of the Maximum Clique Using Eigenvalue Relation | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者名 |
大戸, 康紀
× 大戸, 康紀
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論文では，NP 完全問題の一つである k-Clique 問題の最適化バージョンである最大クリーク問題が多項式時間で解けることを証明します．入力グラフ G を辺に有理数の重みを持つ Undirected graph へ拡張します．すべての辺が重み 1 であり，すべての頂点が他の頂点との間に辺を持つ Subgraph をクリークとします．最大クリークの一つを多項式時間で抽出するアルゴリズムを構成する上で必要な証明を行うとともに，そのアルゴリズムを擬似コードの形で与えます．Adjacency matrix の -1 以下の固有値の個数を km(G) とすると，Cauchy Interlacing Theorem により最大クリークの頂点数 k は km(G) +1 以下となります．アルゴリズムでは，km(G) の変化を用いて，頂点を削除したときに最大クリークサイズを変化させない頂点を削除していきます．このアルゴリズムの計算量は O(n8) です．この結果は complexity class NP と P が同じであることを示しています． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2020-AL-180, 号 23, p. 1-10, 発行日 2020-11-18 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 2188-8566 | |||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
