ABSTRACT
In this paper, we present a self-stabilizing algorithm that concurrently finds two disjoint minimal dominating sets in an arbitrary network graph without any isolated node. The worst case convergence time of the algorithm from any arbitrary initial state is O(n4) where n is the number of nodes in the network.
- Attiya, H. and Welch, J. 1998. Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw-Hill, Hightstown, NJ. Google ScholarDigital Library
- Dolev, S., Israeli, A., and Moran, S. 1993. Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing, 7 (1993), 3--16. Google ScholarDigital Library
- Estrin, D., Govindan, R., Heidemann, J. S, and Kumar, S. 1999. Next century challenges: Scalable coordination in sensor networks. In Mobile Computing and Networking, pages 263--270, 1999. Google ScholarDigital Library
- Hedetniemi, S. M., Hedetniemi, S. T., Jacobs, D. P., and Srimani, P. K. 2003. Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Computers & Mathematics with Applications, 46, 5--6 (2003), 805--811.Google ScholarCross Ref
- Ore, O. Theory of Graphs. 1962. American Mathematical Society, XXXVIII, Providence, R. I.Google Scholar
Index Terms
A self-stabilizing algorithm for two disjoint minimal dominating sets in an arbitrary graph
Recommendations
Self-stabilizing algorithm for two disjoint minimal dominating sets
AbstractWe 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 ...
Highlights- New self-stabilizing algorithm for two disjoint minimal dominating sets in a graph.
- An improvement by a factor of n over the best existing algorithm [2].
- Interleaving of two copies of an algorithm on mutually disjoint state ...
A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets
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-...
Enumerating minimal dominating sets in chordal bipartite graphs
We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is equivalent to enumeration of minimal transversals in ...
Comments