Parallel breadth-first search algorithms for trees and graphs

DOI10.1080/00207168408803413zbMath0534.68045OpenAlexW2140391860MaRDI QIDQ3318124

G. P. Bhattacharjee, Ratan K. Ghosh

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

directed graphparallel algorithmtime complexityundirected graphordered 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) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Theory of operating systems (68N25)

Related Items (8)

Fast parallel graph searching with applications ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ Parallel algorithms for a depth first search and a breadth first search ⋮ Parallel algorithms for connectivity problems in graph theory ⋮ A unified approach to parallel depth-first traversals of general trees ⋮ Breadth-first traversal of trees and integer sorting in parallel ⋮ Parallel search algorithms for graphs and trees ⋮ Efficient parallel algorithms for parameterized problems

Cites Work

• Characterizations of Reducible Flow Graphs
• Parallel Computations in Graph Theory
• New Parallel-Sorting Schemes
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parallel breadth-first search algorithms for trees and graphs