A Distributed Algorithm for Computing the Node Search Number in Trees

David Coudert 1 Florian Huc 2 Dorian Mazauric 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis \emph{et al.}~[EST94]. It can be executed in an asynchronous environment, requires an overall computation time of $O(n\log{n})$, and $n$ messages of $\log_3{n}+4$ bits each. The main contribution of this work lies in the data structure proposed to design our algorithm, called \emph{hierarchical decomposition}. This simple and flexible data structure is used for four operations: updating the node search number after addition or deletion of any tree-edges in a distributed fashion; computing it in a tree whose edges are added sequentially and in any order; computing other graph invariants such as the process number and the edge search number, by changing only initialization rules; extending our algorithms for trees and forests of unknown size (using messages of up to $2\log_3{n}+5$ bits).
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2012, 63 (1), pp.158-190. <10.1007/s00453-011-9524-3>
Liste complète des métadonnées


https://hal.inria.fr/inria-00587819
Contributeur : David Coudert <>
Soumis le : jeudi 21 avril 2011 - 15:37:24
Dernière modification le : mardi 24 janvier 2012 - 18:57:55
Document(s) archivé(s) le : samedi 3 décembre 2016 - 22:02:27

Fichier

paper-noformat.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Florian Huc, Dorian Mazauric. A Distributed Algorithm for Computing the Node Search Number in Trees. Algorithmica, Springer Verlag, 2012, 63 (1), pp.158-190. <10.1007/s00453-011-9524-3>. <inria-00587819>

Partager

Métriques

Consultations de
la notice

245

Téléchargements du document

176