Self-stabilizing minimum-degree spanning tree within one from the optimal degree

Abstract : We propose a self-stabilizing algorithm for constructing a Minimum-Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most ∆∗ + 1, where ∆∗ is the minimum possible maximum degree of a spanning tree of the network. To the best of our knowledge our algorithm is the first self stabilizing solution for the construction of a minimum-degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e. the send/receive atomicity). The time complexity of our solution is O(mn2 log n) where m is the number of edges and n is the number of nodes. The memory complexity is O(δ log n) in the send-receive atomicity model (δ is the maximal degree of the network).
Type de document :
Communication dans un congrès
23rd IEEE International Symposium on Parallel&Distributed Processing (IPDPS 2009), May 2009, Rome, Italy. IEEE, pp.1-11, 2009, 〈10.1109/IPDPS.2009.5161042〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00336713
Contributeur : Lélia Blin <>
Soumis le : mardi 4 novembre 2008 - 18:05:08
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : lundi 7 juin 2010 - 19:38:44

Fichier

SSMDST.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Lélia Blin, Maria Gradinariu Potop-Butucaru, Stephane Rovedakis. Self-stabilizing minimum-degree spanning tree within one from the optimal degree. 23rd IEEE International Symposium on Parallel&Distributed Processing (IPDPS 2009), May 2009, Rome, Italy. IEEE, pp.1-11, 2009, 〈10.1109/IPDPS.2009.5161042〉. 〈inria-00336713〉

Partager

Métriques

Consultations de la notice

372

Téléchargements de fichiers

183