Self-stabilizing algorithm for two disjoint minimal dominating sets

We propose a new self stabilizing algorithm to compute two mutually disjoint minimal dominating sets in an arbitrary graph G with no isolates (this is always possible due to famous Ore's theorem in [1] that says "In a graph having no isolated nodes, the complement of any minimal dominating set is a dominating set"). We use an unfair central daemon and unique ids of the nodes. The time complexity of our algorithm is O(n(3)), an improvement by a factor of n from that of [2], that uses same assumptions to design an O(n(4)) algorithm, where n is the number of nodes in G. The algorithm uses the concept of running two copies of an algorithm in an interleaving manner such that the state spaces of the two copies are always kept mutually disjoint. We expect our approach will prove useful in designing algorithms for other mutually disjoint predicates in a network graph. (C) 2019 Elsevier B.V. All rights reserved.