An optimal distributed depth-first-search algorithm

Abstract

This paper presents a new distributed depth-first-search algorithm with communication and time complexities of O(|V|). The algorithm is shown to use 2|V|-2 messages and 2|V|-2 units of time and is shown to be optimal in time and message.