A self-stabilizing algorithm for optimally efficient sets in graphs

The efficiency of a set S subset of V in a graph G = (V, E), is defined as epsilon(S) = vertical bar{v is an element of V - S: vertical bar N(v) boolean AND S vertical bar = }vertical bar 1; in other words, the efficiency of a set S equals the number of vertices in V - S that are adjacent to exactly one vertex in S. A set S is called optimally efficient if for every vertex v is an element of V - S, epsilon(S boolean OR {v}) <= epsilon(S), and for every vertex u is an element of S, epsilon(S - {u}) < epsilon(S). We present a polynomial time self-stabilizing algorithm for finding an optimally efficient set in an arbitrary graph. This algorithm is designed using the distance-2 self-stabilizing model of computation. (C) 2012 Elsevier B.V. All rights reserved.