A Distributed Algorithm for Computing the Node Search Number in Trees
2012
Abstract
We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis et al. (Inf. Comput. 113(1):50-79, 1994). It can be executed in an asynchronous environment, requires an overall computation time of O(nlog n), and n messages of log (3) n+4 bits each.
Details
Title
A Distributed Algorithm for Computing the Node Search Number in Trees
Author(s)
Coudert, David ; Huc, Florian ; Mazauric, Dorian
Published in
Algorithmica
Volume
63
Pages
158-190
Date
2012
Keywords
Other identifier(s)
View record in Web of Science
Laboratories
DCL
Record Appears in
Scientific production and competences > I&C - School of Computer and Communication Sciences > IINFCOM > DCL - Distributed Computing Laboratory
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date
2012-03-01