Cited By
View all- Zheng QYang CYang HZhou J(2018)A Fast Exact Algorithm for Deployment of Sensor Nodes for Internet of ThingsInformation Systems Frontiers10.1007/s10796-018-9890-322:4(829-842)Online publication date: 8-Dec-2018
A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets
Pages 132 - 138
Abstract
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 ) .
References
[1]
D.W. Bange, A.E. Barkauskas, P.J. Slater, A constructive characterization of trees with two disjoint minimum dominating sets, Congr. Numer., 21 (1978) 101-112.
[2]
E.J. Cockayne, S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math., 15 (1976) 213-222.
[3]
E.W. Dijkstra, Self-stabilizing systems in spite of distributed control, Commun. ACM, 17 (1974) 643-644.
[4]
E.W. Dijkstra, A belated proof of self-stabilization, Distrib. Comput., 1 (1986) 5-6.
[5]
S. Dolev, Self-stabilization, MIT Press, 2000.
[6]
P. Erdös, A.M. Hobbs, C. Payan, Disjoint cliques and disjoint maximal independent sets of vertices in graphs, Discrete Math., 42 (1982) 57-61.
[7]
M. Gairing, W. Goddard, S.T. Hedetniemi, P. Kristiansen, A.A. McRae, Distance-two information in self-stabilizing algorithms, Parallel Process. Lett., 14 (2004) 387-398.
[8]
W. Goddard, S.T. Hedetniemi, D.P. Jacobs, V. Trevisan, Distance-k knowledge in self-stabilizing algorithms, Theoret. Comput. Sci., 399 (2008) 118-127.
[9]
W. Goddard, S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, Z. Xu, Self-stabilizing graph protocols, Parallel Process. Lett., 18 (2008) 189-199.
[10]
N. Guellati, H. Kheddouci, A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs, J. Parallel Distrib. Comput., 70 (2010) 406-415.
[11]
T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[12]
T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs, Advanced Topics, Marcel Dekker, New York, 1998.
[13]
T.W. Haynes, M.A. Henning, Trees with two disjoint minimum independent dominating sets, Discrete Math., 304 (2005) 69-78.
[14]
S.T. Hedetniemi, D.P. Jacobs, K.E. Kennedy, Linear-time self-stabilizing algorithms for disjoint independent sets, Comput. J., 56 (2013) 1381-1387.
[15]
M.A. Henning, C. Lowenstein, D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math., 309 (2009) 6451-6458.
[16]
M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin., 89 (2008) 159-162.
[17]
M. Ikeda, S. Kamei, H. Kakugawa, A space-optimal self-stabilizing algorithm for the maximal independent set problem, in: Proc. 3rd Int. Conf. on Parallel and Distributed Computing, Applications and Technologies, 2002, pp. 70-74.
[18]
J. Kratochvíl, P. Manuel, M. Miller, A. Proskurowski, Disjoint and unfolding domination in graphs, Australas. J. Combin., 18 (1998) 277-292.
[19]
M. Mesbahi, M. Egerstedt, Graph Theoretic Methods in Multiagent Networks, Princeton Univ. Press, 2010.
[20]
O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 1962.
[21]
S.K. Shukla, D.J. Rosenkrantz, S.S. Ravi, Observations on self-stabilizing graph algorithms for anonymous networks, in: Proceedings of the Second Workshop on Self-stabilizing Systems, 1995, pp. 7.1-7.15.
[22]
J. Southey, M.A. Henning, A characterization of graphs with disjoint dominating sets and paired-dominating sets, J. Comb. Optim., 22 (2011) 217-234.
- A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets
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 ...
Well-dominated graphs without cycles of lengths 4 and 5
Let G be a graph. A set S of vertices in Gdominates the graph if every vertex of G is either in S or a neighbor of a vertex in S. Finding a minimum cardinality set which dominates the graph is an NP-complete problem. The graph G is well-dominated if all ...
Disjoint dominating and total dominating sets in graphs
It has been shown [M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159-162] that every connected graph with minimum degree at least two that is not a cycle on five vertices has a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 16 August 2015
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024
Other Metrics
Citations
Cited By
View all- Zheng QYang CYang HZhou J(2018)A Fast Exact Algorithm for Deployment of Sensor Nodes for Internet of ThingsInformation Systems Frontiers10.1007/s10796-018-9890-322:4(829-842)Online publication date: 8-Dec-2018