Parallel depth first search. II: Analysis (Q1116344)

[For part I see ibid. 16, No.6, 479-499 (1987; Zbl 0665.68048).] The paper presents the analysis of the authors' formulation of a parallel depth first search technique (DFS). At the heat of this formulation is a dynamic work-distribution scheme that divides the work between different processors. In order to compare the proposed strategy on models for l-ring, hypercube and shared-memory architectures an isoefficiency function is introduced. If the problem size, W, needs to grow as f(N) to maintain an efficiency E, then f(N) is the isoefficiency function. Furthermore, the concept of isoefficiency is used in characterizing the scalability of parallel algorithms for which linear speedup for arbitrarily many processors can be obtained by simply increasing the problem size.