| 講演名 | 2023-12-22 1-Minimal Minus Domination問題を解決する反復合成に基づく自己安定アルゴリズムについて 山田 塔太(名工大), 金 鎔煥(名工大), 片山 喜章(名工大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本研究では1-Minimal Minus Domination問題を紹介し，その問題を解決する自己安定アルゴリズムを提案する．グラフ$G=(V,E)$の各ノード$i in V$において${-1,0,1}$のいずれかを，$i$と$i$に隣接する全てのノードの値の総和を1以上になるように割り当てる関数をMinus Domination関数と呼ぶ．Minus Domination関数$f$において，$i$に割り当てた値を$1$下げることで$f$がMinus Domination関数となるノード$i(in V)$が存在しないならばMinimal Minus Domination関数と呼ぶ．さらに，$i$に割り当てた値を$1$上げ，$j,k$に割り当てた値を$1$下げることで$f$がMinus Domination関数となるノード$i,j,k(in V)$が存在しないならば，$f$は1-Minimal Minus Domination関数と呼ぶ．本稿では，1-Minimal Minus Domination関数を構築する自己安定アルゴリズムを提案する． |
| 抄録(英) | In this study, we introduce a new problem called the textit{1-Minimal Minus Domination} problem and a self-stabilizing algorithm to solve the problem. A textit{Minus Domination} function is a function to assign a value in ${-1,0,1}$ for each node $i in V$ in graph $G=(V,E)$ such that the sum of the values node $i$ and its all neighbors equal to or greater than $1$．A textit{Minus Domination} function is $emph{minimal}$ if the decrease of any node's value causes the violation of the Minus Domination function. Furthermore, textit{Minus Domination} is a textit{1-Minimal Minus Domination} if there are no three nodes $i,j, $and $k (in V)$ such that another textit{Minus Domination} appears by increasing the value of $i$ by 1 and increasing the values of $j$ and $k$ by 1．In this paper，we propose a self-stabilizing algorithm to find a textit{1-Minimal Minus Domination} function. |
| キーワード(和) | 分散システム / 自己安定アルゴリズム / 反復合成 / Minus Domination |
| キーワード(英) | Distributed System / Self-Stabilizing Algorithm / Loop Composition / Minus Domination |
| 資料番号 | COMP2023-27 |
| 発行日 | 2023-12-15 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2023/12/22(から1日開催) |
| 開催地（和） | 宮崎大学 まちなかキャンパス |
| 開催地（英） | Miyazaki Univ. Machinaka Campus |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 委員長氏名（和） | 宇野 裕之(大阪公立大) |
| 委員長氏名（英） | Hiroyuki Uno(Osaka Metropolitan Univ.) |
| 副委員長氏名（和） | 来嶋 秀治(滋賀大) |
| 副委員長氏名（英） | Shuji Kijima(Shiga Univ.) |
| 幹事氏名（和） | 和佐 州洋(法政大) / 横井 優(東工大) |
| 幹事氏名（英） | Kunihiro Wasa(Hosei Univ.) / Yu Yokoi(Tokyo Inst. of Tech) |
| 幹事補佐氏名（和） | 安藤 映(専修大) |
| 幹事補佐氏名（英） | Ei Ando(Senshu Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 1-Minimal Minus Domination問題を解決する反復合成に基づく自己安定アルゴリズムについて |
| サブタイトル（和） | |
| タイトル（英） | On a Self-Stabilizing Algorithm for a 1-Minimal Minus Domination Based on Loop Composition |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散システム / Distributed System |
| キーワード(2)（和/英） | 自己安定アルゴリズム / Self-Stabilizing Algorithm |
| キーワード(3)（和/英） | 反復合成 / Loop Composition |
| キーワード(4)（和/英） | Minus Domination / Minus Domination |
| 第 1 著者 氏名（和/英） | 山田 塔太 / Tota Yamada |
| 第 1 著者 所属（和/英） | 名古屋工業大学大学院(略称：名工大) Nagoya Institute of Technology(略称：NIT) |
| 第 2 著者 氏名（和/英） | 金 鎔煥 / Yonghwan Kim |
| 第 2 著者 所属（和/英） | 名古屋工業大学大学院(略称：名工大) Nagoya Institute of Technology(略称：NIT) |
| 第 3 著者 氏名（和/英） | 片山 喜章 / Yoshiaki Katayama |
| 第 3 著者 所属（和/英） | 名古屋工業大学大学院(略称：名工大) Nagoya Institute of Technology(略称：NIT) |
| 発表年月日 | 2023-12-22 |
| 資料番号 | COMP2023-27 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | COMP-325 |
| ページ範囲 | pp.68-75(COMP), |
| ページ数 | 8 |
| 発行日 | 2023-12-15 (COMP) |