Publication
Information Processing Letters
Paper

A new distributed Depth-First-Search algorithm

View publication

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.

Date

08 Apr 1985

Publication

Information Processing Letters

Authors

Topics

Share