An improved parallel algorithm that computes the BFS numbering of a directed graph
DOI10.1016/0020-0190(88)90164-0zbMATH Open0658.68081OpenAlexW2088570605MaRDI QIDQ1111392FDOQ1111392
Authors: Hillel Gazit, Gary L. Miller 
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
Recommendations
- Parallel breadth-first search algorithms for trees and graphs
- Parallel algorithms for a depth first search and a breadth first search
- An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
- Efficient parallel algorithms for breadth first spanning forests of general graphs
- Improved processor bounds for parallel algorithms for weighted directed graphs
parallel algorithmbreadth-first searchPRAMfast 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)
Cites Work
Cited In (17)
- A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula
- 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
- Finding smallest supertrees
- Tiling pictures of the plane with dominoes
- A 2-approximation NC algorithm for connected vertex cover and tree cover
- A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle
- On the parallel computation of the biconnected and strongly connected co-components of graphs
- Parallel search algorithms for graphs and trees
- Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
- 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
- Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm
- Improved processor bounds for parallel algorithms for weighted directed graphs
- Sub-cubic cost algorithms for the all pairs shortest path problem
- Efficient parallel algorithms for computing all pair shortest paths in directed graphs
This page was built for publication: An improved parallel algorithm that computes the BFS numbering of a directed graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111392)
