A Self-stabilizing Algorithm for the 1-Minimal Minus Domination Problem
摘要
A Minus Dominating (MD) Function of a graph \(G = (V, E)\) \((|V|=n)\) is a function that assigns a value from \(\{-1,0,1\}\) to each node \(i \in V\) such that the sum of the values of node i and all its neighboring nodes is positive (i.e., equal to or greater than 1). An MD function is minimal if decreasing the value of any node by 1 causes a violation of the conditions of the MD function. As an extension of the MD function, we introduce the k-Minimal Minus Dominating (MMD) Function \((k\ge 0)\) , which is a minimal MD function such that no other MD function can be obtained by increasing the values for some nodes by k in total and decreasing the values for some nodes by at least \(k+1\) in total. Note that any minimal MD function can be referred to as a 0-MMD function. In this paper, we propose a silent self-stabilizing algorithm to solve the 1-Minimal Minus Domination Problem on an arbitrary graph, using a composition technique that repeatedly applies several self-stabilizing algorithms in order, known as loop composition. It converges within \(\mathcal {O}(n(\varDelta ^2+D))\) rounds, where D is the diameter and \(\varDelta \) is the maximum degree of a graph, and each node requires \(\mathcal {O}(\varDelta ^4\log n)\) bits of memory.