文献

J-GLOBAL ID：202002253382794500   整理番号：20A2228318

CONGESTモデルにおける距離2彩色【JST・京大機械翻訳】

Distance-2 Coloring in the CONGEST Model

著者 (3件)： Halldorsson Magnus M. (Reykjavik University, Iceland) ,  Kuhn Fabian (University of Freiburg, Germany) ,  Maus Yannic (Israel Institute of Technology, Israel)
資料名： ACM Proceedings  (ACM Proceedings)
号： PODC ’20  ページ： 233-242  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： CONGESTモデルにおけるグラフGの距離-2頂点彩色を計算するための効率的なランダム化および決定論的分散アルゴリズムを与えた。特に,ΔがGの最大度であるならば,著者らは,O(log Δ log n)ラウンドにおいてΔ2+1色を有するGの距離-2彩色を計算するために,ランダム化CONGESTモデルアルゴリズムがあることを示した。さらに,色の数がいくつかのΔλ_1/ポリログnに対して(1+π*)Δ2にわずかに増加するならば,CONGESTモデルにおけるポリログn時間での距離-2色決定を決定論的に計算できることを示した。最後に,O(Δ2+log*n)ラウンド決定論的CONGESTアルゴリズムを与え,Δ2+1色の距離-2彩色を計算した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *発色 ,  分散アルゴリズム
準シソーラス用語： 決定論 , 【Automatic Indexing@JST】

著者キーワード (4件)： CONGESTモデル ,  距離2彩色 ,  分散グラフ彩色 ,  電力グラフ

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： モデル ,  彩色