A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks - Sorbonne Université
Journal Articles Journal of Combinatorial Optimization Year : 2013

A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks

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 in arbitrary topology networks. Our algorithm is the first self-stabilizing protocol that is specifically designed to approximate an MLST. It builds a solution whose number of leaves is at least 1/3 of the maximum possible in arbitrary graphs. The time complexity of our algorithm is O(n^2) rounds.

Dates and versions

hal-00930035 , version 1 (14-01-2014)

Identifiers

Cite

Sayaka Kamei, Hirostugu Kakugawa, Stéphane Devismes, Sébastien Tixeuil. A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks. Journal of Combinatorial Optimization, 2013, 25 (3), pp.430-459. ⟨10.1007/s10878-011-9383-5⟩. ⟨hal-00930035⟩
353 View
0 Download

Altmetric

Share

More