Parallel depth first search. I: Implementation
The depth-first search (DFS) is one of the most common techniques used in artificial intelligence or for solving various combinatorial problems and constraint satisfaction problems. Since many of the problems solved by DFS are highly computation intensive, there is a great interest in developing parallel versions of this algorithm. The paper presents performance results of a parallel formulation of DFS run on various parallel computers (Sequent Balance 21000, Intel Hypercube and BBN Butterfly). These results clearly show that while retaining the storage efficiency, the DFS can be speeded up by several orders of magnitude. Moreover, if parallel DFS expands fewer nodes than DFS, a speedup of greater than N using N processors can be observed (speedup anomaly). The authors' experiments also show that hypercube and shared- memory architectures are significantly better than the ring architecture. The main conclusion of the research is that the effectiveness of the parallel formulation is strongly influenced by the work distribution scheme and architectural features of the parallel computer system. As general remarks, the paper is self-contained, clear and of high quality. It is intended for specialists or students in final years in the field of artificial intelligence and parallel computers. [For part II see ibid. 16, No.6, 501-519 (1987; Zbl 0665.68049)].
- Parallel depth first search. II: Analysis
- A parallel search algorithm for directed acyclic graphs
- scientific article; zbMATH DE number 1760141
- Parallel depth-bounded discrepancy search
- scientific article; zbMATH DE number 4090815
- A note on parallel depth first search
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- The scalability analysis of a parallel tree search algorithm
- scientific article; zbMATH DE number 1860736
- A general branch and bound formulation for understanding and synthesizing And/Or tree search procedures
- Anomalies in parallel branch-and-bound algorithms
- Depth-first iterative-deepening: An optimal admissible tree search
- General branch and bound, and its relation to A^* and AO^*
- scientific article; zbMATH DE number 4090815 (Why is no real title available?)
- scientific article; zbMATH DE number 3657150 (Why is no real title available?)
- scientific article; zbMATH DE number 3690676 (Why is no real title available?)
- MANIP—A Multicomputer Architecture for Solving Combinatonal Extremum-Search Problems
- Parallel depth first search. II: Analysis
- A note on parallel depth first search
- Parallel depth first search. II: Analysis
- A hybrid VNS/tabu search algorithm for solving the vehicle routing problem with drones and en route operations
- Anytime pack search
- On estimating workload in interval branch-and-bound global optimization algorithms
- Scalable Parallel DFPN Search
- Parallel multithreaded IDA* heuristic search: algorithm design and performance evaluation
- Parallel algorithms for a depth first search and a breadth first search
- scientific article; zbMATH DE number 4090815 (Why is no real title available?)
- scientific article; zbMATH DE number 865205 (Why is no real title available?)
- Exactly solving hard permutation flowshop scheduling problems on peta-scale GPU-accelerated supercomputers
- Random seeking: a general, efficient, and informed randomized scheme for dynamic load balancing
- Graph representation of the fixed route dial-a-ride problem
- Parallel state-space search for a first solution with consistent linear speedups
This page was built for publication: Parallel depth first search. I: Implementation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116343)
