抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
Vertex彩色は,分散計算において研究された古典的対称性破壊問題の1つである。本論文では,O(log*n+Det_d(polylogn))時間で動作するランダム化LOCALモデルにおける(Δ+1)リスト彩色の新しいアルゴリズムを提示し,そこでは,Det_d(n′)は,(deg+1)リスト彩色(v’s palet)の決定論的複雑性であり,n′-頂点グラフ上で(v)+1であった。これはHarris,Schneider,Su(STOC2016)の以前のランダム化アルゴリズムで改善する。複雑性O(√logΔ+loglogn+Det_d(polylogn)),および(Δが十分に大きいとき)は,Fraigniaud,Heinrich,およびKosowski(FOCS2016)の最良既知決定論的アルゴリズムよりはるかに速く,複雑性O(Δεlog25Δ+log*n)を有した。このアルゴリズムは最適であるように見える。それは,Naor(SIDMA1991)によるΩ(log*n)ランダム化下界,および,Detが(Δ+1)リスト着色の決定論的複雑性である,Chang,KopelowitzおよびPettie(FOCS2016)による,Ω(Det(polylogn))ランダム化下界と整合した。Det_d(n′)とDet(n′)に関する最良の既知上限は,PanconesiとSrinivasan(アルゴリズム1996のJournal)による2O(√logn′)であり,両方の問題の複雑性が漸近的に同じであると非常に妥当であった。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
