Eulerian tour construction in a distributed environment
We present an efficient distributed algorithm for constructing an Eulerian tour in a distributed environment. This algorithm requires (1 + r)(\E\ + \V\) messages and time units for constructing an Eulerian circuit, where \E\ is the number of the communication links, \V\ the number of the nodes in the underlying network graph, and 0 less than or equal to r < 1. The value of r depends on the network topology and on the chosen traversal path. In the best case, when r = 0 the algorithm only requires (\E\ + \V\) messages and time units. A simple modification allows us to construct a (noncyclic) tour using (1 + r)(\E\ + 2\V\) messages and time units. (C) 1999 Elsevier Science B.V. All rights reserved.
eulerian tour communication graph distributed systems