講演抄録/キーワード |
講演名 |
2021-05-07 17:10
1-極小独立支配集合を求める反復合成に基づく自己安定アルゴリズム ○谷内優斗(阪大)・首藤裕一(法政大)・泉 泰介・増澤利光(阪大) COMP2021-4 |
抄録 |
(和) |
ネットワークにおける1-極小独立支配集合を求める自己安定アルゴリズムを提案する.1-極小独立支配集合とは,ネットワーク$G = (V,E)$の独立支配集合$S$であって,いかなる$u,v in S$ $(u neq v),w in V setminus S$についても,$S cup { w } setminus { u,v }$が独立支配集合とならないような集合である.本稿では,1-極小独立支配集合を求める問題に対して,各頂点が一意な識別子を持つという仮定の下で動作するサイレントな自己安定アルゴリズムを提案する.提案アルゴリズムは弱公平デーモンの下で動作する.$n$をグラフの頂点数,$D$をグラフの直径とすると,収束時間は$O(nD)$ラウンドであり,1頂点(プロセス)あたりの空間計算量は$O(log n)$ビットである.アルゴリズムの設計にあたって,反復合成と呼ばれる手法を用いる. |
(英) |
We consider the 1-minimal independent dominating set (1-MIDS) problem: given a connected graph $G=(V,E)$, our goal is to find an 1-minimal independent dominating set (1-MIDS) of a given network $G$, that is, an independent dominating set (IDS) $S subset V$ of $G$ such that $S cup { w } setminus { u,v }$ is not an independent dominating set for any nodes $u,v in S$, and $w notin S$ ($u neq v$). We give a silent, self-stabilizing, and asynchronous distributed algorithm for this problem, assuming each node has unique identifiers. Our algorithm works under the textit{weakly-fair daemon}. The time complexity of our algorithm is $O(nD)$ rounds and the space complexity is $O(log n)$ bits per node (process), where $n$ is the number of nodes in the network and $D$ is the diameter of the network. We use a composition technique called textit{loop composition}. |
キーワード |
(和) |
分散システム / 自己安定アルゴリズム / 反復合成 / 1-極小独立支配集合 / / / / |
(英) |
distributed system / self-stabilizing algorithm / loop composition / 1-minimal independent dominating set / / / / |
文献情報 |
信学技報, vol. 121, no. 11, COMP2021-4, pp. 23-30, 2021年5月. |
資料番号 |
COMP2021-4 |
発行日 |
2021-04-30 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2021-4 |
|