| 大会名称 |
|---|
| 2020年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2020 |
| 発行日 |
| 2020-08-18 |
| セッション番号 |
| 126 |
| セッション名 |
| アルゴリズムとソフトウェア工学 |
| 講演日 |
| 2020/09/02 |
| 講演場所(会議室等) |
| 第4イベント会場 |
| 講演番号 |
| TCS-5-1 |
| タイトル |
| 最小次数全域木問題に対する分散アルゴリズム |
| 著者名 |
| 泉 泰介, |
| キーワード |
| 抄録 |
| 最小次数全域木問題は、最大次数が最も小さくなるような全域木を構成する問題であり、無線通信におけるストリーム配信のスループット最大化等の応用を持つ。本研究では、同問題に対する、計算時間がノード数に対する準線形であり、かつ定数近似率保証を持つ初めての分散アルゴリズムを提案した。 |