| Item type |
SIG Technical Reports(1) |
| 公開日 |
2021-08-18 |
| タイトル |
|
|
タイトル |
分散計算における誘導サイクル発見問題の下界 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Lower Bounds for Induced Cycle Detection in Distributed Computing |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
名古屋大学大学院多元数理科学研究科 |
| 著者所属 |
|
|
|
名古屋大学大学院多元数理科学研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Mathematics, Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Mathematics, Nagoya University |
| 著者名 |
ルガル, フランソワ
宮本, 昌幸
|
| 著者名(英) |
Francois, Le Gall
Masayuki, Miyamoto
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
部分グラフ発見問題は入力ネットワークが特定のグラフを部分グラフとして持つかを判定する問題である．本研究では分散計算モデルでの誘導サイクル発見問題についての下界を導出する．この結果は既知の誘導部分グラフ 発見問題の上界に漸近的に一致するものである． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
The distributed subgraph detection asks, for a fixed graph ????, whether the ????-node input graph contains ???? as a subgraph or not. In this paper, we show lower bounds for induced cycle detection in a standard distributed computing model. These results asymptotically match the known upper bounds of induced subgraph detection. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2021-AL-184,
号 2,
p. 1-8,
発行日 2021-08-18
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL21184002.pdf (922.1 kB)
