SELF-STABILIZING VERTEX COVER IN ANONYMOUS NETWORKS WITH OPTIMAL APPROXIMATION RATIO
Abstract
This paper presents a deterministic self-stabilizing algorithm that approximates a minimum vertex cover in anonymous networks with ratio 2 using the distributed scheduler and the link-register model with composite atomicity. No algorithm with a better approximation ratio can exist. The algorithm stabilizes in O(min{n, Δ2, Δ log3 n}) rounds and requires O(Δ) memory per node.
References
D. Angluin , Local and global properties in networks of processors, STOC '80: 12th An. ACM Symp. on Theory of Computing (ACM, New York, 1980) pp. 82–93. Google ScholarS. K. Shukla , D. J. Rosenkrantz and S. S. Ravi , Observations on self-stabilizing graph algorithms for anonymous networks, 2nd Workshop on Self-Stabilizing Systems (1995) pp. 7.1–7.15. Google ScholarW. Goddard , S. T. Hedetniemi and Z. Shi , An anonymous self-stabilizing algorithm for 1-maximal matching in trees, PDPTA, ed.H. R. Arabnia (CSREA Press, 2006) pp. 797–803. Google Scholar- Inf. Process. Lett. 43(2), 77 (1992), DOI: 10.1016/0020-0190(92)90015-N. Crossref, ISI, Google Scholar
- Inf. Process. Lett. 91(2), 77 (2004), DOI: 10.1016/j.ipl.2004.03.010. Crossref, ISI, Google Scholar
- J. ACM 48(4), 798 (2001), DOI: 10.1016/j.ipl.2004.03.010. Crossref, ISI, Google Scholar
M. Hańćkowiak , M. Karoński and A. Panconesi , On the distributed complexity of computing maximal matchings, SODA '98: 9th An. ACM-SIAM Symp. on Discrete Algorithms (Philadelphia, 1998) pp. 219–225. Google ScholarS. Chattopadhyay , L. Higham and K. Seyffarth , Dynamic and self-stabilizing distributed matching, 21st An. Symp. on Principles of distributed computing (ACM, New York, 2002) pp. 290–297. Google Scholar- Theo. Comp. Science 410(14), 1336 (2009), DOI: 10.1016/j.tcs.2008.12.022. Crossref, ISI, Google Scholar
- J. Kiniwa. Approximation of self-stabilizing vertex cover less than 2. In T. Herman and S. Tixeuil, editors, Self-Stabilizing Systems, volume 3764 of LNCS, pp. 171–182. Springer, 2005 . Google Scholar
F. Kuhn , T. Moscibroda and R. Wattenhofer , What cannot be computed locally!, PODC '2004: 23rd An. ACM Symp. on Principles of Distributed Computing (New York, 2004) pp. 300–309. Google Scholar- ACM Trans. Algorithms 5(1), 1 (2008), DOI: 10.1145/1435375.1435381. Crossref, ISI, Google Scholar
-
V. Turau and B. Hauck , A self-stabilizing approximation algorithm for vertex cover in anonymous networks , SSS 2009: 11th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems . Google Scholar -
V. Polishchuk , A local 2-approximation algorithm for the vertex cover problem , 23rd Int. Symp. on Distributed Computing (DISC) . Google Scholar - J. ACM 32(4), 804 (1985), DOI: 10.1145/4221.4227. Crossref, ISI, Google Scholar
-
S. Dolev , Self-Stabilization ( MIT Press , Cambridge, USA , 2000 ) . Crossref, Google Scholar - Distrib. Comput. 7(1), 3 (1993), DOI: 10.1007/BF02278851. Crossref, ISI, Google Scholar
-
D. S. Hochbaum (ed.) , Approximation algorithms for NP-hard problems ( PWS Publishing Co. , Boston, USA , 1997 ) . Google Scholar


