WEKO3
アイテム
An Optimal Algorithm for Finding All the Cliques
https://ipsj.ixsq.nii.ac.jp/records/32671
https://ipsj.ixsq.nii.ac.jp/records/32671bc82f7ff-4f7e-41ad-b43b-0b3474dedd2b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL89012013.pdf (977.9 kB)
|
Copyright (c) 1989 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1989-11-20 | |||||||
| タイトル | ||||||||
| タイトル | An Optimal Algorithm for Finding All the Cliques | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An Optimal Algorithm for Finding All the Cliques | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| Department of Communications and Systems The University of Electro - Communications | ||||||||
| 著者所属 | ||||||||
| Presently with TOYOTA Motor Corporation. | ||||||||
| 著者所属 | ||||||||
| Department of Communications and Systems The University of Electro - Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Communications and Systems The University of Electro - Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Presently with TOYOTA Motor Corporation. | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Communications and Systems The University of Electro - Communications | ||||||||
| 著者名 |
Etsuji, Tomita
× Etsuji, Tomita
|
|||||||
| 著者名(英) |
Etsuji, Tomita
× Etsuji, Tomita
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We present an algorithm for finding all the cliques of an undirected graph. It is a very simple backtracking searching algorithm whose basic techniques are based upon Bron and Kerbosch's and it outputs the cliques found in a tree-like form. Then we prove that its worst-case time complexity is O(3^＆ｌｔ；n/3＆ｇｔ；)=O(2^＆ｌｔ；n/1.89...＆ｇｔ；)=O(1.44^＆ｌｔ；...n＆ｇｔ；) for an n-vertex graph. This is optimal with respect to n since there exist up to 3 ^＆ｌｔ；n/3＆ｇｔ； cliques in an n-vertex graph. It is noted that a slight modification of this algorithm gives an O(2^＆ｌｔ；n/2.98＆ｇｔ；)-time simple algorithm for finding only one maximum clique. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We present an algorithm for finding all the cliques of an undirected graph. It is a very simple backtracking searching algorithm, whose basic techniques are based upon Bron and Kerbosch's, and it outputs the cliques found in a tree-like form. Then we prove that its worst-case time complexity is O(3^＆ｌｔ；n/3＆ｇｔ；)=O(2^＆ｌｔ；n/1.89...＆ｇｔ；)=O(1.44^＆ｌｔ；...n＆ｇｔ；) for an n-vertex graph. This is optimal with respect to n since there exist up to 3 ^＆ｌｔ；n/3＆ｇｔ； cliques in an n-vertex graph. It is noted that a slight modification of this algorithm gives an O(2^＆ｌｔ；n/2.98＆ｇｔ；)-time simple algorithm for finding only one maximum clique. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1989, 号 98(1989-AL-012), p. 91-98, 発行日 1989-11-20 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
