Abstract
The maximum leaf spanning tree (MLST) is a good candidate for constructing a virtual backbone in self-organized multihop wireless networks, but is practically intractable (NP-complete). Self-stabilization is a general technique that permits to recover from catastrophic transient failures in self-organized networks without human intervention. We propose a fully distributed self-stabilizing approximation algorithm for the MLST problem on arbitrary topology networks. Our algorithm is the first self-stabilizing protocol that is specifically designed for the construction of an MLST. It improves other previous self-stabilizing solutions both for generality (arbitrary topology graphs vs. unit disk graphs or generalized disk graphs, respectively) and for approximation ratio, as it guarantees the number of its leaves is at least 1/3 of the maximum one. The time complexity of our algorithm is O(n 2) rounds.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 441–452. Springer, Heidelberg (1998)
Tixeuil, S.: Self-stabilizing Algorithms. Chapman & Hall/CRC Applied Algorithms and Data Structures. In: Algorithms and Theory of Computation Handbook, 2nd edn. Taylor & Francis, Abington (2009)
Galbiati, G., Maffioli, F., Morzenti, A.: A short note on the approximability of the maximum leaves spanning tree problem. Information Processing Letters 52(1), 45–49 (1994)
Lu, H.I., Ravi, R.: Approximating maximum leaf spanning trees in almost linear time. Journal of algorithms 29, 132–141 (1998)
Blin, L., Potop-Butucaru, M., Rovedakis, S.: Self-stabilizing minimum-degree spanning tree within one from the optimal degree. In: Proceedings of the 23th IEEE International Parallel and Distributed Processing Symposium (2009)
Blin, L., Potop-Butucaru, M.G., Rovedakis, S., Tixeuil, S.: A new self-stabilizing minimum spanning tree construction with loop-free property. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 407–422. Springer, Heidelberg (2009)
Butelle, F., Lavault, C., Bui, M.: A uniform self-stabilizing minimum diameter tree algorithm. In: Helary, J.-M., Raynal, M. (eds.) WDAG 1995. LNCS, vol. 972, pp. 257–272. Springer, Heidelberg (1995)
Guha, S., Khuller, S.: Approximation Algorithms for Connected Dominating Sets. Algorithmica 20, 347–387 (1998)
Kamei, S., Kakugawa, H.: A self-stabilizing distributed approximation algorithm for the minimum connected dominating set. In: Proceedings of the 9th IPDPS Workshop on Advances in Parallel and Distributed Computational Models, p. 224 (2007)
Raei, H., Tabibzadeh, M., Ahmadipoor, B., Saei, S.: A self-stabilizing distributed algorithm for minimum connected dominating sets in wireless sensor networks with different transmission ranges. In: Proceedings of the 11th International Conference on Advanced Communication Technology, pp. 526–530 (2009)
Dolev, S.: Self-Stabilization. The MIT Press, Cambridge (2000)
Datta, A.K., Larmore, L.L., Vemula, P.: Self-stabilizing leader election in optimal space. In: Kulkarni, S., Schiper, A. (eds.) SSS 2008. LNCS, vol. 5340, pp. 109–123. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kamei, S., Kakugawa, H., Devismes, S., Tixeuil, S. (2010). A Self-stabilizing 3-Approximation for the Maximum Leaf Spanning Tree Problem in Arbitrary Networks. In: Thai, M.T., Sahni, S. (eds) Computing and Combinatorics. COCOON 2010. Lecture Notes in Computer Science, vol 6196. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14031-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-14031-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14030-3
Online ISBN: 978-3-642-14031-0
eBook Packages: Computer ScienceComputer Science (R0)