講演名 | 2020-05-09 Another time-complexity analysis for the maximal clique enumeration algorithm CLIQUES 富田 悦次(電通大), アレッシオ コンテ(ピサ大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | We revisit the maximal clique enumeration algorithm CLIQUES that appeared in Theoretical Computer Science 2006. It is proved to work in $O(3^{n/3})$-time in the worst-case for an $n$ vertex graph. In this note, we extend the time-complexity analysis with respect to the number of maximal cliques, an issue that was left as an open problem since TCS 2006. |
抄録(英) | We revisit the maximal clique enumeration algorithm CLIQUES that appeared in Theoretical Computer Science 2006. It is proved to work in $O(3^{n/3})$-time in the worst-case for an $n$ vertex graph. In this note, we extend the time-complexity analysis with respect to the number of maximal cliques, an issue that was left as an open problem since TCS 2006. |
キーワード(和) | maximal clique / maximal independent set / enumeration / algorithm / time-complexity / delay |
キーワード(英) | maximal clique / maximal independent set / enumeration / algorithm / time-complexity / delay |
資料番号 | COMP2020-1 |
発行日 | 2020-05-02 (COMP) |
研究会情報 | |
研究会 | COMP / IPSJ-AL |
---|---|
開催期間 | 2020/5/9(から1日開催) |
開催地(和) | 国立情報学研究所 |
開催地(英) | National Institute of Informatics |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | 藤戸 敏弘(豊橋技科大) |
委員長氏名(英) | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
副委員長氏名(和) | 中野 眞一(群馬大) |
副委員長氏名(英) | Shinichi Nakano(Gunma Univ.) |
幹事氏名(和) | 大舘 陽太(名大) / 玉置 卓(兵庫県立大) |
幹事氏名(英) | Yota Otachi(Nagoya Univ) / Suguru Tamaki(Univ. of Hyogo) |
幹事補佐氏名(和) | 脊戸 和寿(成蹊大) |
幹事補佐氏名(英) | Kazuhisa Seto(Seikei Univ.) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
---|---|
本文の言語 | ENG |
タイトル(和) | |
サブタイトル(和) | |
タイトル(英) | Another time-complexity analysis for the maximal clique enumeration algorithm CLIQUES |
サブタイトル(和) | |
キーワード(1)(和/英) | maximal clique / maximal clique |
キーワード(2)(和/英) | maximal independent set / maximal independent set |
キーワード(3)(和/英) | enumeration / enumeration |
キーワード(4)(和/英) | algorithm / algorithm |
キーワード(5)(和/英) | time-complexity / time-complexity |
キーワード(6)(和/英) | delay / delay |
第 1 著者 氏名(和/英) | 富田 悦次 / Etsuji Tomita |
第 1 著者 所属(和/英) | 電気通信大学(略称:電通大) The University of Electro-Communications(略称:Univ. Electro-Comm.) |
第 2 著者 氏名(和/英) | アレッシオ コンテ / Alessio Conte |
第 2 著者 所属(和/英) | ピサ大学(略称:ピサ大) Univarsity of Pisa(略称:Univ. of Pisa) |
発表年月日 | 2020-05-09 |
資料番号 | COMP2020-1 |
巻番号(vol) | vol.120 |
号番号(no) | COMP-13 |
ページ範囲 | pp.1-8(COMP), |
ページ数 | 8 |
発行日 | 2020-05-02 (COMP) |