An improved parallel algorithm that computes the BFS numbering of a directed graph
From MaRDI portal
Publication:1111392
DOI10.1016/0020-0190(88)90164-0zbMath0658.68081OpenAlexW2088570605MaRDI QIDQ1111392
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(88)90164-0
parallel algorithmPRAMbreadth-first searchfast matrix multiplicationconcurrent-read concurrent-writeexclusive-read exclusive-write parallel random access machine
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (16)
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph ⋮ An efficient parallel algorithm for finding rectangular duals of plane triangular graphs ⋮ On the parallel computation of the biconnected and strongly connected co-components of graphs ⋮ Tiling pictures of the plane with dominoes ⋮ A 2-approximation NC algorithm for connected vertex cover and tree cover ⋮ Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion ⋮ Sub-cubic cost algorithms for the all pairs shortest path problem ⋮ A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle ⋮ A randomized NC algorithm for the maximal tree cover problem ⋮ Efficient parallel algorithms for path problems in directed graphs ⋮ A model classifying algorithms as inherently sequential with applications to graph searching ⋮ Efficient parallel algorithms for computing all pair shortest paths in directed graphs ⋮ A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula ⋮ Parallel search algorithms for graphs and trees ⋮ Improved processor bounds for parallel algorithms for weighted directed graphs ⋮ Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm
Cites Work
This page was built for publication: An improved parallel algorithm that computes the BFS numbering of a directed graph
