**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**33030

##### A New Self-stabilizing Algorithm for Maximal 2-packing

**Authors:**
Zhengnan Shi

**Abstract:**

**Keywords:**
self-stabilization,
2-packing,
distributed computing,
fault tolerance,
graph algorithms

**Digital Object Identifier (DOI):**
doi.org/10.5281/zenodo.1081683

**References:**

[1] Y. Afek and S. Dolev. Local stabilizer. J. Parallel Distrib. Comput., 62(5):745-765, 2002.

[2] J. Beauquier, A. K. Datta, M. Gradinariu, and F. Magniette. Selfstabilizing local mutual exclusion and daemon refinement. In International Symposium on Distributed Computing, pages 223-237, 2000.

[3] E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Comm. ACM, 17(11):643-644, Jan. 1974.

[4] S. Dolev. Self-Stabilization. MIT Press, 2000.

[5] S. Dolev, A. Israeli, and S. Moran. Uniform dynamic self-stabilizing leader election. IEEE Trans. on Parallel and Distributed Systems, 8(4), 1995.

[6] W. Goddard, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani. Selfstabilizing algorithms for orderings and colorings. International Journal of Foundations of Computer Science, 16:19-36, 2005.

[7] S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani. Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Comput. Math. Appl., 46(5-6):805-811, 2003.

[8] D. S. Hochbaum and D. B. Schmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180-184, 1985.

[9] S.-C. Hsu and S.-T. Huang. A self-stabilizing algorithm for maximal matching. Inform. Process. Lett., 43:77-81, 1992.

[10] A. Meir and J. W. Moon. Relations between packing and covering numbers of a tree. Pacific Journal of Mathematics, 61(1):225-233, 1975.

[11] A. Panconesi and A. Srinivasan. The local nature of -coloring and its algorithmic applications. Combinatorica, 15:225-280, 1995.

[12] S. Rajagopalan and V. Vazirani. Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM J. Comput., 28:525-540, 1998.

[13] Z. Shi, W. Goddard, and S. T. Hedetniemi. an anonymous selfstabilizing algorithm for 1-maximal independent set in trees. Information Processing Letters, 91(2):77-83, 2004.

[14] S. Shukla, D. Rosenkrantz, and S. Ravi. Observations on self-stabilizing graph algorithms for anonymous networks. In Proceedings of the Second Workshop on Self-Stabilizing Systems, pages 7.1-7.15, 1995.

[15] G. Tel. Introduction to Distributed Algorithms, Second Edition. Cambridge University Press, Cambridge UK, 2000.