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

atomic treeBreadth-First Spanning Treesdirected graphordered treesparallel algorithmParallel Breadth-First Search algorithmsshared memory modelSIMDSingle Instruction-stream Multiple Data-stream computertime complexityundirected graph

Mathematics Subject Classification ID

Theory of operating systems (68N25) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

• Characterizations of Reducible Flow Graphs
• Depth-First Search and Linear Graph Algorithms
• 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?)
• New Parallel-Sorting Schemes
• Parallel Computations in Graph Theory

Cited in

(23)

• Fast parallel graph searching with applications
• An improved parallel algorithm that computes the BFS numbering of a directed graph
• Parallel depth first search. II: Analysis
• A unified approach to parallel depth-first traversals of general trees
• Breadth-first traversal of trees and integer sorting in parallel
• A model classifying algorithms as inherently sequential with applications to graph searching
• Conflict-free broadcasting algorithms for graph traversals and their applications
• Parallel search algorithms for graphs and trees
• Efficient parallel algorithms for parameterized problems
• An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
• On the parameterized parallel complexity and the vertex cover problem
• scientific article; zbMATH DE number 5734730 (Why is no real title available?)
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Parallel algorithms for a depth first search and a breadth first search
• Efficient parallel algorithms for breadth first spanning forests of general graphs
• Parallel algorithms for connectivity problems in graph theory
• scientific article; zbMATH DE number 88969 (Why is no real title available?)
• scientific article; zbMATH DE number 1960881 (Why is no real title available?)
• Theory and techniques for synthesizing efficient breadth-first search algorithms
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Shared-memory parallel frontier-based search
• Unrestricted and complete breadth-first search of trapezoid graphs in O(n) time
• Recognizing breadth-first search trees in linear time

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)