文献

J-GLOBAL ID：202002245279648024   整理番号：20A1865907

コーダルグラフにおける短い発表分散最小頂点彩色と最大独立集合【JST・京大機械翻訳】

Brief Announcement Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

著者 (2件)： Konrad Christian (University of Bristol, Bristol, United Kingdom) ,  Zamaraev Viktor (Durham University, Durham, United Kingdom)
資料名： ACM Proceedings  (ACM Proceedings)
号： PODC ’18  ページ： 159-161  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： LOCALモデルの弦グラフ上の最小Vertex色と最大独立集合に対する決定論的分布(1+ε)近似アルゴリズムを与えた。著者らの彩色アルゴリズムは,O(1/εlogn)ラウンドで実行して,著者らの独立集合アルゴリズムは,O(1εlog(1/ε)log’n)ラウンドの実行時間を有した。着色に対して,既存の下限は1/εとlognへの依存性が最良であることを意味する。独立セットに対して,Ω(1/ε)ラウンドが必要であることを証明した。両アルゴリズムは入力弦グラフのツリー分解を利用する。それらは,入力グラフのツリー分解によって同定される間隔部分グラフを繰り返し剥離し,それによって頂点集合をO(logn)層に分割する。着色のために,各間隔グラフは独立に着色され,それは層間のさまざまな彩色矛盾をもたらす。次に,これらのコンフリクトを,分割の特殊構造を用いて,別の相で解決する。独立セットでは,それらが既に大きな独立集合を含むので,最初のO(log1/ε)層のみが必要とされる。区間グラフのための(1+ε)近似最大独立集合アルゴリズムを開発し,次にそれらの層に適用した。本研究は,有用なツリー分解が分散コンピューティングに対してどのように役立つかという疑問を提起する。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】

著者キーワード (5件)： 近似アルゴリズム ,  弦グラフ ,  局所モデル ,  最大独立集合 ,  最小頂点彩色

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 頂点 ,  彩色 ,  集合