| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-03-08 11:30 ［招待講演］Tight Distributed Listing of Cliques Keren Censor-Hillel（Technion）・Yi-Jun Chang（ETH）・○François Le Gall（Nagoya Univ.）・Dean Leitersdorf（Technion）  COMP2020-31 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | Much progress has recently been made in understanding the complexity landscape of subgraph finding problems in the CONGEST model of distributed computing. However, so far, very few tight bounds are known in this area. For triangle (i.e., 3-clique) listing, an optimal $tilde{O}(n^{1/3})$-round distributed algorithm has been constructed by Chang et al. [SODA 2019, PODC 2019]. Recent works have shown sublinear algorithms for $K_p$-listing, for each $p geq 4$, but still leaving a significant gap between the upper bounds and the known lower bounds of the problem. In this work, we completely close this gap. We show that for each $p geq 4$, there is an $tilde{O}(n^{1 - 2/p})$-round distributed algorithm that lists all $p$-cliques $K_p$ in the communication network. Our algorithm is optimal up to a polylogarithmic factor, due to the $tilde{Omega}(n^{1 - 2/p})$-round lower bound of Fischer et al. [SPAA 2018], which holds even in the CONGESTED CLIQUE model. Together with the triangle-listing algorithm by Chang et al. [SODA 2019, PODC 2019], our result thus shows that the round complexity of $K_p$-listing, for all $p$, is the same in both the CONGEST and CONGESTED CLIQUE models, at $tilde{Theta}(n^{1 - 2/p})$ rounds. For $p=4$, our result additionally matches the $tilde{Omega}(n^{1/2})$ lower bound for $K_4$-emph{detection} by Czumaj and Konrad [DISC 2018], implying that the round complexities for detection and listing of $K_4$ are equivalent in the CONGEST model. |
|
| キーワード | （和） | 分散計算 / 分散アルゴリズム / グラフ問題 / クリーク / / / / |
| （英） | Distributed computing / Distributed algorithms / Graph problems / Cliques / / / / | |
| 文献情報 | 信学技報, vol. 120, no. 426, COMP2020-31, pp. 24-24, 2021年3月. | |
| 資料番号 | COMP2020-31 | |
| 発行日 | 2021-03-01 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2020-31 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2021-03-08 - 2021-03-08 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2021-03-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Tight Distributed Listing of Cliques |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 分散計算 / Distributed computing |
| キーワード(2)（和/英） | 分散アルゴリズム / Distributed algorithms |
| キーワード(3)（和/英） | グラフ問題 / Graph problems |
| キーワード(4)（和/英） | クリーク / Cliques |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | Keren Censor-Hillel / Keren Censor-Hillel / |
| 第1著者 所属（和/英） | Technion (略称： テクニオン イスラエル工科大) Technion (略称： Technion) |
| 第2著者 氏名（和/英/ヨミ） | Yi-Jun Chang / Yi-Jun Chang / |
| 第2著者 所属（和/英） | ETH (略称： ETH) ETH (略称： ETH) |
| 第3著者 氏名（和/英/ヨミ） | François Le Gall / François Le Gall / |
| 第3著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第4著者 氏名（和/英/ヨミ） | Dean Leitersdorf / Dean Leitersdorf / |
| 第4著者 所属（和/英） | Technion (略称： テクニオン イスラエル工科大) Technion (略称： Technion) |
| 講演者 | 第3著者 |
| 発表日時 | 2021-03-08 11:30:00 |
| 発表時間 | 60分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2020-31 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.426 |
| ページ範囲 | p.24 |
| ページ数 | 1 |
| 発行日 | 2021-03-01 (COMP) |
[研究会発表申込システムのトップページに戻る]