A self-stabilizing algorithm for optimally efficient sets in graphs

作者：Hedetniemi Sandra M; Hedetniemi Stephen T; Jiang Hao; Kennedy K E^*; McRae Alice A

来源：Information Processing Letters, 2012, 112(16): 621-623.

DOI：10.1016/j.ipl.2012.02.014

• Self-stabilizing algorithms
• Graph algorithms
• Optimally efficient set

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}) %26lt;= epsilon(S), and for every vertex u is an element of S, epsilon(S - {u}) %26lt; 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.

• 出版日期2012-8-31