×

Self-stabilizing algorithms for unfriendly partitions into two disjoint dominating sets. (English) Zbl 1284.05288

Summary: An unfriendly partition is a partition of the vertices of a graph \(G = (V,E)\) into two sets, say Red \(R(V)\) and Blue \(B(V)\), such that every Red vertex has at least as many Blue neighbors as Red neighbors, and every Blue vertex has at least as many Red neighbors as Blue neighbors. We present three polynomial time, self-stabilizing algorithms for finding unfriendly partitions in arbitrary graphs \(G\), or equivalently into two disjoint dominating sets.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/0095-8956(90)90092-E · Zbl 0717.05065 · doi:10.1016/0095-8956(90)90092-E
[2] DOI: 10.1016/j.dam.2005.10.014 · Zbl 1095.68073 · doi:10.1016/j.dam.2005.10.014
[3] DOI: 10.1016/0095-8956(77)90037-5 · Zbl 0336.05104 · doi:10.1016/0095-8956(77)90037-5
[4] DOI: 10.7151/dmgt.1241 · Zbl 1068.05051 · doi:10.7151/dmgt.1241
[5] DOI: 10.1145/361179.361202 · Zbl 0305.68048 · doi:10.1145/361179.361202
[6] DOI: 10.1007/BF01843566 · Zbl 0604.68015 · doi:10.1007/BF01843566
[7] DOI: 10.1016/S0012-365X(99)00131-4 · Zbl 0947.05058 · doi:10.1016/S0012-365X(99)00131-4
[8] DOI: 10.7151/dmgt.1230 · Zbl 1064.05112 · doi:10.7151/dmgt.1230
[9] DOI: 10.1142/S0129626404001970 · Zbl 02218303 · doi:10.1142/S0129626404001970
[10] DOI: 10.1016/S0377-2217(99)00459-2 · Zbl 0965.90053 · doi:10.1016/S0377-2217(99)00459-2
[11] Gerber M. U., Australas. J. Combin. 29 pp 201– (2004)
[12] Goddard W., LNCS 4056 pp 349– (2006)
[13] DOI: 10.1016/j.tcs.2008.02.009 · Zbl 1146.68057 · doi:10.1016/j.tcs.2008.02.009
[14] Haynes T. W., FL pp 303– (2002)
[15] Hedetniemi S. M., J. Combin. Math. Combin. Comput. 48 pp 157– (2004)
[16] Kristiansen P., FL pp 308– (2002)
[17] Rodriguez-Velazquez J. A., AKCE Internat. J. Graphs Combin. 4 (1) pp 83– (2007)
[18] Shafique K. H., Congr. Numer. 154 pp 183– (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.