Parallel breadth-first search algorithms for trees and graphs

DOI10.1080/00207168408803413MaRDI QIDQ3318124zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

parallel algorithmdirected graphundirected graphtime complexityordered treesSIMDshared memory modelatomic treeBreadth-First Spanning TreesParallel Breadth-First Search algorithmsSingle Instruction-stream Multiple Data-stream computer

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3606484 (Why is no real title available?)
• scientific article; zbMATH DE number 3635515 (Why is no real title available?)
• Characterizations of Reducible Flow Graphs
• Depth-First Search and Linear Graph Algorithms
• New Parallel-Sorting Schemes
• Parallel Computations in Graph Theory

Cited in

(22)

• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Efficient parallel algorithms for parameterized problems
• Parallel algorithms for connectivity problems in graph theory
• 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
• scientific article; zbMATH DE number 1960881 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 88969 (Why is no real title available?)
• Parallel search algorithms for graphs and trees
• Breadth-first traversal of trees and integer sorting in parallel
• scientific article; zbMATH DE number 5734730 (Why is no real title available?)
• 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

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)