A Distributed Algorithm for Computing the Node Search Number in Trees

作者：Coudert David; Huc Florian; Mazauric Dorian^*

来源：Algorithmica, 2012, 63(1-2): 158-190.

DOI：10.1007/s00453-011-9524-3

• Distributed algorithm
• Edge search number
• Graph searching
• Node search number
• Pathwidth
• Process number

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. %26lt;br%26gt;The main contribution of this work lies in the data structure proposed to design our algorithm, called 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 2log (3) n+5 bits).

• 出版日期2012-6
• 单位INRIA