文献

J-GLOBAL ID：201702229308303300   整理番号：17A1149396

極小支配集合問題の一般化とその自己安定アルゴリズム

A generalization of the minimal dominating set problem and its self-stabilizing algorithm

著者 (3件)： KOBAYASHI Hisaki (Osaka Univ., JPN) ,  KAKUGAWA Hirotsugu (Osaka Univ., JPN) ,  MASUZAWA Toshimitsu (Osaka Univ., JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 176(COMP2017 13-19)  ページ： 25-32  発行年： 2017年08月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 自己安定システムとは,どのような状況から実行を開始しても,いずれ正当な状況に収束することを保証する分散システムである。また分散システムにおけるk-支配集合とは,各ノードがその集合に含まれる,もしくはその集合に属するk個以上のノードに隣接するような集合である。本稿では,k-支配集合問題を一般化した新たな問題を提案し,同期式ネットワーク上で動作する自己安定アルゴリズムを紹介する。一般化支配集合Dでは,各ノードに支配希望集合C_i={Wⁱ₁,Wⁱ₂,...:Wⁱ_x⊆N_i}(N_i:ノードiの隣接ノード集合)が与えられ,各ノードiはDに含まれる,もしくはあるWⁱ_x(∈C_i)に属するノードがDに含まれる。さらにアルゴリズムの収束時間が高々Ο(n)ラウンド(n:ノード数)であることも示す。(著者抄録)

シソーラス用語： *集合 ,  *グラフ理論 ,  *アルゴリズム ,  収束 ,  *分散系 ,  システムモデル ,  安定化 ,  定理証明 ,  性能評価 ,  ネットワーク
準シソーラス用語： *極小支配集合 ,  *自己安定アルゴリズム ,  自己安定化 ,  同期式ネットワーク

分類 (2件)： 計算理論  (JB02000A) ,  システム・制御理論一般  (IA02010H)

引用文献 (15件)：

• E. W. Dijkstra. Self-stabilizing systems in spite of dis-tributed control. Communications of the ACM 17(11), pp.643-644, 1974.
• G. Wang, H. Wang, X. Tao, J. Zhang. A self-stabilizing algorithm for finding a minimal k-dominating set in general networks. In Proceedings of the International Conference on Data and Knowledge Engineering, pp.74-85, 2012.
• G. Wang, H. Wang, X. Tao, J. Zhang and J. Zhang. Min-imising k-dominating set in arbitrary network graphs. In Proceedings of the 9th International Conference on Ad-vanced Data Mining and Applications, pp.120-132, 2013.
• J. F. Fink and M. S. Jacobson. N-domination in graphs. John Wiley and Sons, 1985.
• N. Guellati and H. Kheddouci. A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. Journal of Parallel and Distributed Computing 70(4), pp.406-415, 2010.

タイトルに関連する用語 (5件)： 支配集合 ,  問題 ,  一般化 ,  自己 ,  アルゴリズム