| Item type |
SIG Technical Reports(1) |
| 公開日 |
2021-04-30 |
| タイトル |
|
|
タイトル |
1-極小独立支配集合を求める反復合成に基づく自己安定アルゴリズム |
| タイトル |
|
|
言語 |
en |
|
タイトル |
A Self-Stabilizing 1-minimal Independent Dominating Set Algorithm Based on Loop Composition |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
阪大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
法政大学情報科学部 |
| 著者所属 |
|
|
|
阪大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
阪大学大学院情報科学研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Osaka University |
| 著者所属(英) |
|
|
|
en |
|
|
Faculty of Computer and Information Sciences, Hosei University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Osaka University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Osaka University |
| 著者名 |
谷内, 優斗
首藤, 裕一
泉, 泰介
増澤, 利光
|
| 著者名(英) |
Yuto, Taniuchi
Yuichi, Sudo
Taisuke, Izumi
Toshimitsu, Masuzawa
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
ネットワークにおける 1-極小独立支配集合を求める自己安定アルゴリズムを提案する．1-極小独立支配集合とは，ネットワーク G = (V，E) の独立支配集合 S であって，いかなる u，v ∈ S (u v)，w ∈ V ＼ S についても，S ∪ {w}＼ {u, v} が独立支配集合とならないような集合である．本稿では，1-極小独立支配集合を求める問題に対して，各頂点が一意な識別子を持つという仮定の下で動作するサイレントな自己安定アルゴリズムを提案する．提案アルゴリズムは弱公平デーモンの下で動作する．n をグラフの頂点数，D をグラフの直径とすると，収束時間は O(nD) ラウンドであり，1 頂点（プロセス）あたりの空間計算量は O(log n) ビットである．アルゴリズムの設計にあたって，反復合成と呼ばれる手法を用いる． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2021-AL-183,
号 9,
p. 1-8,
発行日 2021-04-30
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL21183009.pdf (2.7 MB)
