Parallel depth first search. II: Analysis

DOI10.1007/BF01389001MaRDI QIDQ1116344zbMATH OpenOpenAlexFDO

Authors Vipin Kumar, V. Nageshwara Rao

Publication date 1987

Published in International Journal of Parallel Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01389001

zbMATH Keywords

depth first searchisoefficiency functionparallel algorithmswork-distribution scheme

Mathematics Subject Classification ID

Theory of operating systems (68N25) Theory of software (68N99) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Review text

[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.

Recommendations

• Parallel depth first search. I: Implementation
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Planar Depth-First Search in O(\log n) Parallel Time
• Parallel algorithms for a depth first search and a breadth first search
• Parallel breadth-first search algorithms for trees and graphs

Cites work

• Anomalies in parallel branch-and-bound algorithms
• Depth-first iterative-deepening: An optimal admissible tree search
• scientific article; zbMATH DE number 4033059 (Why is no real title available?)
• scientific article; zbMATH DE number 4090815 (Why is no real title available?)
• scientific article; zbMATH DE number 3657150 (Why is no real title available?)
• MANIP—A Multicomputer Architecture for Solving Combinatonal Extremum-Search Problems
• On Maintaining Dynamic Information in a Concurrent Environment
• Parallel depth first search. I: Implementation

Cited in

(19)

• Parallel depth first search. I: Implementation
• Efficient algorithms for parallel sorting on mesh multicomputers
• Parallel processing for difficult combinatorial optimization problems
• \texttt{mplrs}: a scalable parallel vertex/facet enumeration code
• Could we use a million cores to solve an integer program?
• An optimization of tree topology based parallel cryptography
• A hybrid VNS/tabu search algorithm for solving the vehicle routing problem with drones and en route operations
• Anytime pack search
• scientific article; zbMATH DE number 1639653 (Why is no real title available?)
• Scalable Parallel DFPN Search
• An Event-Driven Algorithm for Agents on the Web
• scientific article; zbMATH DE number 5642148 (Why is no real title available?)
• Parallel algorithms for a depth first search and a breadth first search
• On the scalability of PSRS algorithm
• scientific article; zbMATH DE number 865205 (Why is no real title available?)
• The scalability analysis of a parallel tree search algorithm
• Scalability limits of Bag-of-Tasks applications running on hierarchical platforms
• Parallel state-space search for a first solution with consistent linear speedups
• Metrics for evaluation of parallel efficiency toward highly parallel processing

This page was built for publication: Parallel depth first search. II: Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116344)