A self-stabilizing algorithm for optimally efficient sets in graphs

详细信息    查看全文

• 作者：S ; ra M. Hedetniemi ; Stephen T. Hedetniemi ; Hao Jiang ; K.E. Kennedy ; Alice A. McRae
• 关键词：Self-stabilizing algorithms ; Graph algorithms ; Optimally efficient set
• 刊名：Information Processing Letters
• 出版年：2012
• 出版时间：31 August, 2012
• 年：2012
• 卷：112
• 期：16
• 页码：621-623
• 全文大小：120 K

文摘

The efficiency of a set in a graph , is defined as ; in other words, the efficiency of a set S equals the number of vertices in that are adjacent to exactly one vertex in S. A set S is called optimally efficient if for every vertex , , and for every vertex , . 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.