A self-stabilizing distributed algorithm for the bounded lattice domination problems under the distance-2 model期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

A self-stabilizing distributed algorithm for the bounded lattice domination problems under the distance-2 model

Authors:	Hirotsugu Kakugawa Sayaka Kamei

Affiliation:	1. Faculty of Advanced Science and Technology, Ryukoku University, Otsu, Shiga, Japan;2. Department of Information Engineering, Hiroshima University, Higashi Hiroshima, Hiroshima, Japan

Abstract:	The domination problem is one of the fundamental graph problems, and there are many variations. In this article, we propose a new problem called the minus $(L, K, Z) $$ left(L,K,Zright) $$$ -domination problem where $L, K $$ L,K $$$ , and $Z $$ Z $$$ are integers such that $L \leq - 1 $$ Lle -1 $$$ , $K \geq 1 $$ Kge 1 $$$ , and $Z \geq 1 $$ Zge 1 $$$ . The problem is to assign a value from $L, L + 1, \dots, 0, \dots, K - 1, K $$ L,L+1,dots, 0,dots, K-1,K $$$ for each vertex in a graph such that the local summation of values is greater than or equal to $Z $$ Z $$$ . We also propose a framework named the bounded lattice domination for a class of domination problems, including the minus $(L, K, Z) $$ left(L,K,Zright) $$$ -domination problem. Then, we present a self-stabilizing distributed algorithm under the distance-2 model for the bounded lattice domination. Here, self-stabilization is a class of fault-tolerant distributed algorithms that tolerate transient faults. The time complexity for convergence is , where is the number of processes in a network if the cardinality of the domain of process values is finite and constant. Otherwise, the time complexity for convergence is .

Keywords:	combinatorial optimization distributed algorithm dominating set minus domination self-stabilization

设为首页 | 免责声明 | 关于勤云 | 加入收藏