| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2021-05-07 - 2021-05-08 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2021-05-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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.) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-05-07 17:10:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2021-4 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.11 |
| ページ範囲 | pp.23-30 |
| ページ数 | 8 |
| 発行日 | 2021-04-30 (COMP) |
[研究会発表申込システムのトップページに戻る]