DISTRIBUTED ALGORITHMS FOR DEPTH-FIRST SEARCH

We present distributed algorithms for constructing a depth-first searc h tree for a communication network which are more efficient than previ ous methods. Our algorithms require 2\V\ - 2 messages and units of tim e in the worst case, where \V\ is the number of sites in the network, and as little as \V\ messages and time units in the best case. The act ual number of messages and time units depends on the network topology and possibly on the routing chosen. We can interpret this to mean that the number of messages and time units is \V\(1 + r) in the worst case , where 0 less than or equal to r < 1 and the value of r depends on th e topology and the routing. In a best case for the simplest algorithm, for example when the underlying network has a ring topology, r = O an d our basic algorithm requires \V\ messages and time units, regardless of routing. We extend the basic algorithm to achieve the same best ca se bound for other topologies. The worst case bound, which has r = 1 - 2/\V\, applies if the network topology is a tree. The improvement ove r the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length.