抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
分散メッセージパッシングモデルにおけるグラフ彩色と関連問題を考察した。{Locial-反復アルゴリズム}は,この設定において特に重要である。これらは各頂点が1ホップ近傍における現在の色の関数としてのみその次の色を決定するアルゴリズムである。STOC’93 SzegedyとVishwanathanでは,任意の局所反復(Delta+1)着色アルゴリズムがOmega(Delta log Delta+log ε>n)ラウンドを必要とし,”非常に効率的に還元される”サイト{SV93}である”非常に特別なタイプの彩色”がなければ,あることを示した。”Celta+1(Delta+1)-coloringアルゴリズムには,Omega(Delta log Delta+log Hubbard n)ラウンドが必要であることを示した。本論文では,この特殊なタイプの彩色を得る。特に,著者らは,走行時間O(Delta+log^*n),すなわち,{以下}Szegedy-Vishwanahan障壁による局所反復(Delta+1)着色アルゴリズムを考案した。これは,この障壁が局所反復アルゴリズムに対する固有の限界ではないことを示す。その結果,動的,自己安定化および帯域幅制限設定に対する顕著な改善も達成した:(Delta+1)-頂点色,(2Delta-1)エッジカラー化,最大独立集合,およびO(Delta+log|Σn)時間による最大マッチングに対する自己安定化分散アルゴリズムを得た。”Welta+1”-betex-coloring,(2Delta-1)-edge-coloring,最大独立集合,およびO(Delta+log^*n)時間による最大マッチング。これは,O(n)またはより大きな走行時間サイト{GK10}を有する以前に知られた結果を著しく改善し,O(Delta+log^*n)時間とO(Delta+logn)時間を有するBit-Roundモデルで,CONGESTモデルにおける(2Delta-1)エッジカラー化アルゴリズムを考案するものである。”GK10}は,O(Delta+log^*n)時間を有するCONGESTモデルにおいて,(2Delta-1)エッジカラー化アルゴリズムを考案する。”O(Delta+log n)時間,およびO(Delta+log n)時間を有するBit-Roundモデルにおいて,(2Delta-1)-エッジ着色アルゴリズムを考案した。以前に知られているアルゴリズムは,これらのモデルにおける(2Delta-1)エッジカラー化のために,Deltaに対して超線形依存性を持ち,著者らは,実行時間O(√Delta+log λ>n)を有するarb欠損彩色アルゴリズムを得た。PODC’15サイト{B15}とFraigniaud et al.からのBarenboimの最近の最先端の限界を,多対数因子によるFOCS’16 cite{FHK16}から改良する適切な彩色を計算するために用い,-Ourアルゴリズムは,サイト{HKMS15}のSET-LOCALモデルに適用可能である。【JST・京大機械翻訳】
