文献

J-GLOBAL ID：202002277367211286   整理番号：20A1867575

有界拡大のグラフクラスに関する分散支配【JST・京大機械翻訳】

Distributed Domination on Graph Classes of Bounded Expansion

著者 (4件)： Akhoondian Amiri Saeed (Max-Planck-Institut fuer Informatik, Saarbrucken, Germany) ,  Ossona de Mendez Patrice (CAMS (CNRS UMR 8557), EHESS, Paris, France) ,  Rabinovich Roman (Technische Universitaat Berlin, Berlin, Germany) ,  Siebertz Sebastian (University of Warsaw, Warsaw, Poland)
資料名： ACM Proceedings  (ACM Proceedings)
号： SPAA ’18  ページ： 143-151  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 著者らは,有界拡張のグラフクラスに関する(連結)距離-r支配集合問題のための新しい定数因子近似アルゴリズムを提供した。有界拡張のクラスは,平面グラフや除外(トポロジー)マイナーを持つグラフのようなスパースグラフの多くのよく知られたクラスを含み,特に,これらのクラスは,距離-r支配集合問題に対する逐次定数因子近似アルゴリズムが現在知られているグラフの最も一般的な部分グラフ閉クラスを形成する。提案アルゴリズムは,分散コンピューティングの最上位モデルに実装でき,Oof(r2logn)通信ラウンドを使用する。独立した興味の可能性がある%の技術は,有界拡張クラス上の小半径のスパース近傍カバーの分散計算に基づいている。著者らは,≒estbcモデルにおけるいくつかの関数~数f_fに対して,Oof(r2log n)通信ラウンドにおける有界拡張のあらゆるクラスに関して,半径~2rおよびオーバーラップf(r)のr-近傍カバーを計算する方法を示した。最後に,任意の距離-r支配集合を,有界拡張の任意のクラスで3r+1ラウンドで,常に大きな連結距離-r支配集合に変換するために,局所モデルのより大きな電力を使用する方法を示した。本アルゴリズムを結合して,例えば,Lenzenらの平面グラフに関する支配集合のための定数因子近似アルゴリズムによって,局所モデルにおける一定数のラウンドにおける平面グラフ上の連結支配集合のための定数因子近似アルゴリズムについて,近似比がLenzenらのアルゴリズムのものよりわずか6倍大きかった。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件)： 近似 ,  有界展開 ,  分散コンピューティング ,  支配的な集合 ,  グラフ理論

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

タイトルに関連する用語 (5件)： 有界 ,  拡大 ,  グラフ ,  クラス ,  支配