Parallel depth first search. Part II. Analysis

Vipin Kumar, V. Nageshwara Rao

Research output: Contribution to journalArticlepeer-review

120 Scopus citations


This paper presents the analysis of a parallel formulation of depth-first search. At the heart of this parallel formulation is a dynamic work-distribution scheme that divides the work between different processors. The effectiveness of the parallel formulation is strongly influenced by the work-distribution scheme and the target architecture. We introduce the concept of isoefficiency function to characterize the effectiveness of different architectures and work-distribution schemes. Many researchers considered the ring architecture to be quite suitable for parallel depth-first search. Our analytical and experimental results show that hypercube and shared-memory architectures are significantly better. The analysis of previously known work-distribution schemes motivated the design of substantially improved schemes for ring and shared-memory architectures. In particular, we present a work-distribution algorithm that guarantees close to optimal performance on a shared-memory/ω-network-with-message-combining architecture (e.g. RP3). Much of the analysis presented in this paper is applicable to other parallel algorithms in which work is dynamically shared between different processors (e.g., parallel divide-and-conquer algorithms). The concept of isoefficiency is useful in characterizing the scalability of a variety of parallel algorithms.

Original languageEnglish (US)
Pages (from-to)501-519
Number of pages19
JournalInternational Journal of Parallel Programming
Issue number6
StatePublished - Dec 1987


  • Parallel algorithm
  • depth-first search
  • isoefficiency function
  • work distribution schemes


Dive into the research topics of 'Parallel depth first search. Part II. Analysis'. Together they form a unique fingerprint.

Cite this