| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2019-12-13 09:25 反復合成を用いた1-極大独立集合問題を解く自己安定アルゴリズム ○田中秀幸・首藤裕一（阪大）・角川裕次（龍谷大）・増澤利光（阪大）・Ajoy K. Datta（UNLV）  COMP2019-30 |
|
| 抄録 | （和） | ネットワークの1-極大独立集合を求める自己安定アルゴリズムを提案する．1-極大独立集合とは，無向グラフ(つまり，ネットワーク)$G=(V,E)$の極大独立点集合$S$であって，任意の頂点$u ¥in S, v,w ¥notin S$ ($v ¥neq w$)について$S ¥cup ¥{v,w¥} ¥setminus ¥{u¥}$が独立点集合とならないようなものである．本稿では，1-極大独立集合を求める問題に対して，グラフの各頂点が一意の識別子を持つという仮定のもと動作するサイレント(silent)な自己安定アルゴリズムを提案する．提案アルゴリズムは弱公平分散デーモンのもとで動作する．$n$をグラフの頂点数，$D$をグラフの直径とすると，収束時間は$O(nD)$であり，1頂点あたりの空間計算量は$O(¥log n)$ビットである．これらのアルゴリズムの設計にあたって，反復合成と呼ばれる手法を用いる． |
| （英） | We consider the 1-maximal independent set (1-MIS) problem: given a connected graph $G=(V,E)$, our goal is to find an 1-maximal independent set (1-MIS) of a given network $G$, that is, a maximal independent set (MIS) $S ¥subset V$ of $G$ such that $S ¥cup ¥{v,w¥} ¥setminus ¥{u¥}$ is not an independent set for any nodes $u ¥in S$, and $v,w ¥notin S$ ($v ¥neq w$). We give a silent, self-stabilizing, and asynchronous distributed algorithm to construct 1-MIS on a network of any topology. We assume the processes have unique identifiers and the scheduler is unfair and distributed. The time complexity, i.e., the number of rounds to reach a legitimate configuration in the worst case, of the proposed algorithm is $O(nD)$, where $n$ is the number of processes in the network and $D$ is the diameter of the network. We use a composition technique called loop composition [Datta et.al., 2017] to iterate the same procedure consistently, which results in a small space complexity, $O(¥log n)$ bits per process. |
|
| キーワード | （和） | 分散システム / 自己安定アルゴリズム / 反復合成 / 1-極大独立集合 / / / / |
| （英） | distributed system / self-stabilizing algorithm / loop composition / 1-maximal independent set / / / / | |
| 文献情報 | 信学技報, vol. 119, no. 340, COMP2019-30, pp. 9-16, 2019年12月. | |
| 資料番号 | COMP2019-30 | |
| 発行日 | 2019-12-06 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2019-30 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2019-12-13 - 2019-12-13 |
| 開催地（和） | 群馬大学 伊香保研修所 |
| 開催地（英） | Ikaho Seminar House, Gunma University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2019-12-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 反復合成を用いた1-極大独立集合問題を解く自己安定アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A Self-Stabilizing 1-maximal Independent Set Algorithm |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 分散システム / distributed system |
| キーワード(2)（和/英） | 自己安定アルゴリズム / self-stabilizing algorithm |
| キーワード(3)（和/英） | 反復合成 / loop composition |
| キーワード(4)（和/英） | 1-極大独立集合 / 1-maximal independent set |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 田中 秀幸 / Hideyuki Tanaka / タナカ ヒデユキ |
| 第1著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 首藤 裕一 / Yuichi Sudo / スドウ ユウイチ |
| 第2著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 角川 裕次 / Hirotsugu Kakugawa / カクガワ ヒロツグ |
| 第3著者 所属（和/英） | 龍谷大学 (略称： 龍谷大) Ryukoku University (略称： Ryukoku Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 増澤 利光 / Toshimitsu Masuzawa / マスザワ トシミツ |
| 第4著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第5著者 氏名（和/英/ヨミ） | Ajoy K. Datta / Ajoy K. Datta / |
| 第5著者 所属（和/英） | University of Nevada, Las Vegas (略称： UNLV) University of Nevada, Las Vegas (略称： UNLV) |
| 講演者 | 第1著者 |
| 発表日時 | 2019-12-13 09:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2019-30 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | no.340 |
| ページ範囲 | pp.9-16 |
| ページ数 | 8 |
| 発行日 | 2019-12-06 (COMP) |
[研究会発表申込システムのトップページに戻る]