A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets

作者：Hedetniemi Stephen T; Jacobs David P^*; Kennedy K E

来源：Theoretical Computer Science, 2015, 593: 132-138.

DOI：10.1016/j.tcs.2015.06.004

• Graph
• Self-stabilizing algorithm
• Minimal dominating set
• Maximal independent set

A theorem of Ore [20] states that if D is a minimal dominating set in a graph G = (V, E) having no isolated nodes, then V - D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B. We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7], yielding running times of O (n(2)m).

• 出版日期2015-8-16