講演名 2021-05-07
1-極小独立支配集合を求める反復合成に基づく自己安定アルゴリズム
谷内 優斗(阪大), 首藤 裕一(法政大), 泉 泰介(阪大), 増澤 利光(阪大),
PDFダウンロードページ PDFダウンロードページへ
抄録(和) ネットワークにおける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
資料番号 COMP2021-4
発行日 2021-04-30 (COMP)

研究会情報
研究会 COMP / IPSJ-AL
開催期間 2021/5/7(から2日開催)
開催地(和) オンライン開催
開催地(英) Online
テーマ(和)
テーマ(英)
委員長氏名(和) 増澤 利光(阪大)
委員長氏名(英) Toshimitsu Masuzawa(Osaka Univ.)
副委員長氏名(和) 小野 廣隆(名大)
副委員長氏名(英) Hirotaka Ono(Nagoya Univ)
幹事氏名(和) 大下 福仁(奈良先端大) / 安藤 映(専修大)
幹事氏名(英) Fukuhito Ooshita(NAIST) / Ei Ando(Senshu Univ.)
幹事補佐氏名(和) 大舘 陽太(名大)
幹事補佐氏名(英) Yota Otachi(Nagoya Univ)

講演論文情報詳細
申込み研究会 Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms
本文の言語 JPN
タイトル(和) 1-極小独立支配集合を求める反復合成に基づく自己安定アルゴリズム
サブタイトル(和)
タイトル(英) A self-stabilizing 1-minimal independent dominating set algorithm based on loop composition
サブタイトル(和)
キーワード(1)(和/英) 分散システム / distributed system
キーワード(2)(和/英) 自己安定アルゴリズム / self-stabilizing algorithm
キーワード(3)(和/英) 反復合成 / loop composition
キーワード(4)(和/英) 1-極小独立支配集合 / 1-minimal independent dominating set
第 1 著者 氏名(和/英) 谷内 優斗 / Yuto Taniuchi
第 1 著者 所属(和/英) 大阪大学(略称:阪大)
Osaka University(略称:Osaka Univ.)
第 2 著者 氏名(和/英) 首藤 裕一 / Yuichi Sudo
第 2 著者 所属(和/英) 法政大学(略称:法政大)
Hosei University(略称:Hosei Univ.)
第 3 著者 氏名(和/英) 泉 泰介 / Taisuke Izumi
第 3 著者 所属(和/英) 大阪大学(略称:阪大)
Osaka University(略称:Osaka Univ.)
第 4 著者 氏名(和/英) 増澤 利光 / Toshimitsu Masuzawa
第 4 著者 所属(和/英) 大阪大学(略称:阪大)
Osaka University(略称:Osaka Univ.)
発表年月日 2021-05-07
資料番号 COMP2021-4
巻番号(vol) vol.121
号番号(no) COMP-11
ページ範囲 pp.23-30(COMP),
ページ数 8
発行日 2021-04-30 (COMP)