Parallel breadth-first search algorithms for trees and graphs
DOI10.1080/00207168408803413zbMATH Open0534.68045OpenAlexW2140391860MaRDI QIDQ3318124FDOQ3318124
Authors: Ratan K. Ghosh, G. P. Bhattacharjee 
Publication date: 1984
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207168408803413
Recommendations
- Parallel algorithms for a depth first search and a breadth first search
- Efficient parallel algorithms for breadth first spanning forests of general graphs
- Parallel search algorithms for graphs and trees
- scientific article; zbMATH DE number 88969
- An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
parallel algorithmdirected graphundirected graphtime complexityordered treesSIMDshared memory modelatomic treeBreadth-First Spanning TreesParallel Breadth-First Search algorithmsSingle Instruction-stream Multiple Data-stream computer
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Theory of operating systems (68N25)
Cites Work
Cited In (22)
- Parallel algorithms for connectivity problems in graph theory
- Efficient parallel algorithms for parameterized problems
- Theory and techniques for synthesizing efficient breadth-first search algorithms
- An improved parallel algorithm that computes the BFS numbering of a directed graph
- Recognizing breadth-first search trees in linear time
- A unified approach to parallel depth-first traversals of general trees
- Fast parallel graph searching with applications
- Shared-memory parallel frontier-based search
- Efficient parallel algorithms for breadth first spanning forests of general graphs
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- Title not available (Why is that?)
- An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
- Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time
- Title not available (Why is that?)
- Parallel search algorithms for graphs and trees
- Breadth-first traversal of trees and integer sorting in parallel
- Title not available (Why is that?)
- Parallel algorithms for a depth first search and a breadth first search
- Parallel depth first search. II: Analysis
- Conflict-free broadcasting algorithms for graph traversals and their applications
- On the parameterized parallel complexity and the vertex cover problem
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
This page was built for publication: Parallel breadth-first search algorithms for trees and graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3318124)
