A new distributed Depth-First-Search algorithm

Abstract

This paper presents a new distributed Depth-First-Search (DFS) algorithm for an asynchronous communication network, whose communication and time complexities are O(|E|) and O(|V|), respectively. The output of the algorithm is the DFS tree, kept in a distributed fashion. The existing algorithm, due to Cheung (1983), requires O(|E|) both in communication and time complexities. © 1985.