講演抄録/キーワード |
講演名 |
2023-12-22 16:25
1-Minimal Minus Domination問題を解決する反復合成に基づく自己安定アルゴリズムについて ○山田塔太・金 鎔煥・片山喜章(名工大) COMP2023-27 |
抄録 |
(和) |
本研究では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 / / / / |
文献情報 |
信学技報, vol. 123, no. 325, COMP2023-27, pp. 68-75, 2023年12月. |
資料番号 |
COMP2023-27 |
発行日 |
2023-12-15 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2023-27 |
研究会情報 |
研究会 |
COMP |
開催期間 |
2023-12-22 - 2023-12-22 |
開催地(和) |
宮崎大学 まちなかキャンパス |
開催地(英) |
Miyazaki Univ. Machinaka Campus |
テーマ(和) |
理論計算機科学,一般 |
テーマ(英) |
Theoretical Computer Science, etc |
講演論文情報の詳細 |
申込み研究会 |
COMP |
会議コード |
2023-12-COMP |
本文の言語 |
日本語 |
タイトル(和) |
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 |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第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) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2023-12-22 16:25:00 |
発表時間 |
25分 |
申込先研究会 |
COMP |
資料番号 |
COMP2023-27 |
巻番号(vol) |
vol.123 |
号番号(no) |
no.325 |
ページ範囲 |
pp.68-75 |
ページ数 |
8 |
発行日 |
2023-12-15 (COMP) |
|