Fast parallel graph searching with applications

DOI10.1007/BF01934690zbMath0645.68071OpenAlexW2065654278MaRDI QIDQ1103409

Pranay Chaudhuri

Publication date: 1988

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01934690

zbMATH Keywords

fast parallel algorithmstime complexitydirected acyclic graphsSIMD computeractivity-on-edge networkbreadth-depth searchminimum-depth searchminimum-weighted pathsunbounded shared memory

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 (4)

Finding maximum matching for bipartite graphs in parallel ⋮ FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS ⋮ An adaptive parallel algorithm for analyzing activity networks ⋮ A unified approach to parallel depth-first traversals of general trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for some graph problems on a distributed computational model
• Depth-first search is inherently sequential
• Prallel algorithms for analyzing activity networks
• Parallel computation and conflicts in memory access
• Parallel breadth-first search algorithms for trees and graphs
• Parallel algorithms for a depth first search and a breadth first search
• An 0(log n) parallel algorithm for strong connectivity augmentation problem
• Finding the maximum, merging, and sorting in a parallel computation model
• Parallel Matrix and Graph Algorithms
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Parallel Computations in Graph Theory
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: Fast parallel graph searching with applications