A Distributed Algorithm for Computing the Node Search Number in Trees

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.


Publié dans:
Algorithmica, 63, 158-190
Année
2012
Mots-clefs:
Laboratoires:




 Notice créée le 2012-03-01, modifiée le 2019-12-05


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)