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 , Laboratoire I3S - 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).
Document type :
Journal articles
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00587819
Contributor : David Coudert <>
Submitted on : Thursday, April 21, 2011 - 3:37:24 PM
Last modification on : Monday, September 9, 2019 - 1:42:09 PM
Long-term archiving on : Saturday, December 3, 2016 - 10:02:27 PM

File

paper-noformat.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

389

Files downloads

478