| Item type |
デフォルトアイテムタイプ_（フル）(1) |
| 公開日 |
2025-01-27 |
| タイトル |
|
|
タイトル |
Self-stabilizing 2-minimal dominating set algorithms based on loop composition |
|
言語 |
en |
| 作成者 |
Maruyama, Syohei
Sudo, Yuichi
Kamei, Sayaka
Kakugawa, Hirotsugu
|
| アクセス権 |
|
|
アクセス権 |
embargoed access |
|
アクセス権URI |
http://purl.org/coar/access_right/c_f1cf |
| 権利情報 |
|
|
言語 |
en |
|
権利情報 |
© 2023. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/ |
| 権利情報 |
|
|
言語 |
en |
|
権利情報 |
This is not the published version. Please cite only the published version. |
| 権利情報 |
|
|
言語 |
ja |
|
権利情報 |
この論文は出版社版ではありません。引用の際には出版社版をご確認、ご利用ください。 |
| 主題 |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
Dominating set |
| 主題 |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
Self-stabilization |
| 主題 |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
Loop composition |
| 主題 |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
2-minimality |
| 主題 |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
Girth |
| 内容記述 |
|
|
内容記述 |
Given a graph G = (V,E), a 2-minimal dominating set (2-MDS) of G is a minimal dominating set D ⊆ V such that D \ {pi, pj} ∪ {pz} is not a dominating set for any nodes pi, pj ∈ D (pi ̸= pj ) and pz ̸∈ D. We propose two silent self-stabilizing asynchronous distributed algorithms to find a 2-MDS. In both algorithms, we assume the weakly fair distributed daemon and that the processes have unique identifiers. The first one is for the general networks. The time complexity is O(nH) rounds, and the space complexity is O(Δ log n) bits per process, where n is the number of processes, H is the diameter of the network, and Δ is the maximum degree. The second one is for the networks of girth at least 7. The girth is the length of the shortest cycles in the network. The time complexity is O(nH) rounds, and the space complexity is O(log n) bits per process. |
|
言語 |
en |
| 出版者 |
|
|
出版者 |
Elsevier |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 関連情報 |
|
|
関連タイプ |
isVersionOf |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1016/j.tcs.2023.114314 |
| 助成情報 |
|
|
|
助成機関名 |
日本学術振興会 |
|
|
言語 |
ja |
|
|
研究課題番号URI |
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-19K11826/ |
|
|
研究課題番号 |
19K11826 |
|
|
研究課題名 |
外乱に対して安定な分散アルゴリズムの相互作用パターン |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
Japan Society for the Promotion of Science |
|
|
言語 |
en |
|
|
研究課題番号URI |
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-19K11828/ |
|
|
研究課題番号 |
19K11828 |
|
|
研究課題名 |
外乱に対して安定な分散アルゴリズムの相互作用パターン |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
日本学術振興会 |
|
|
言語 |
ja |
|
|
研究課題番号URI |
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-19H04085/ |
|
|
研究課題番号 |
19H04085 |
|
|
研究課題名 |
動的ネットワークにおける動的タスクのための適応的な耐故障性を持つ分散アルゴリズム |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
Japan Society for the Promotion of Science |
|
|
言語 |
en |
|
|
研究課題番号URI |
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-20H04140/ |
|
|
研究課題番号 |
20H04140 |
|
|
研究課題名 |
動的ネットワークにおける動的タスクのための適応的な耐故障性を持つ分散アルゴリズム |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
日本学術振興会 |
|
|
言語 |
ja |
|
|
研究課題番号URI |
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-23K28037/ |
|
|
研究課題番号 |
23H03347 |
|
|
研究課題名 |
情報の不確かさに着目した大規模動的分散システムの新たな理論的基盤とその応用 |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
Japan Society for the Promotion of Science |
|
|
言語 |
en |
|
|
研究課題番号URI |
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-23K11059/ |
|
|
研究課題番号 |
23K11059 |
|
|
研究課題名 |
New theoretical basis of large scale dynamic distributed systems based on uncertain information and its applications |
|
|
言語 |
en |
| 助成情報 |
|
|
|
助成機関名 |
日本学術振興会 |
|
|
言語 |
ja |
|
|
研究課題番号URI |
https://projectdb.jst.go.jp/search/?kw=JPMJFR226U |
|
|
研究課題番号 |
JPMJFR226U |
|
|
研究課題名 |
障害から超高速に自律復旧するナノスケールネットワークの設計 |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
Japan Society for the Promotion of Science |
|
|
言語 |
en |
|
|
研究課題名 |
障害から超高速に自律復旧するナノスケールネットワークの設計 |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
日本学術振興会 |
|
|
言語 |
ja |
|
|
研究課題名 |
動的ネットワークにおける多様な故障に対する耐性を持つ分散アルゴリズム |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
Japan Society for the Promotion of Science |
|
|
言語 |
en |
|
|
研究課題名 |
動的ネットワークにおける多様な故障に対する耐性を持つ分散アルゴリズム |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
日本学術振興会 |
|
|
言語 |
ja |
|
|
研究課題名 |
動的自律分散システムにおけるプロセス選出のための相互作用パターンの解明 |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
Japan Society for the Promotion of Science |
|
|
言語 |
en |
|
|
研究課題名 |
動的自律分散システムにおけるプロセス選出のための相互作用パターンの解明 |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
科学技術振興機構 |
|
|
言語 |
ja |
|
|
研究課題名 |
自己安定アルゴリズムの飛躍的発展に向けた研究 |
|
|
言語 |
ja |
| 助成情報 |
|
|
|
助成機関名 |
Japan Science and Technology Agency |
|
|
言語 |
en |
|
|
研究課題名 |
自己安定アルゴリズムの飛躍的発展に向けた研究 |
|
|
言語 |
ja |
| 開始ページ |
|
|
開始ページ |
114314 |
| 書誌情報 |
en : Theoretical Computer Science
巻 983,
p. 114314,
発行日 2023-11-20
|
| 旧ID |
56160 |
| 備考 |
The full-text file will be made open to the public on 20 November 2025 in accordance with publisher's 'Terms and Conditions for Self-Archiving' |
TCS_983_114314.pdf (1.8 MB)
