Parallel strong orientation of an undirected graph
From MaRDI portal
In the shared memory model, a parallel algorithm is presented to solve the following graph problem: find a strong orientation for a given undirected 2-connected graph. The algorithm runs in \(O(\log^ 2n)\) time on \(O(n^ 3)\) processors, where n is the number of points of the graph. If write conflicts are solved in a reasonable way, the time complexity can be lowered to O(log n).
Recommendations
- An optimal parallel processor bound in strong orientation of an undirected graph
- Parallel strong orientation on a mesh connected computer
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Parallel algorithms for connectivity problems in graph theory
- Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
Cites work
Cited in
(8)- An optimal parallel processor bound in strong orientation of an undirected graph
- On efficient parallel strong orientation
- Parallel strong orientation on a mesh connected computer
- Parallel search algorithms for graphs and trees
- On the optimal strongly connected orientations of city street graphs. IV: Four east-west avenues or north-south streets
- Parallel algorithms for connectivity problems in graph theory
- Fast parallel strong orientation of mixed graphs and related augmentation problems
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
This page was built for publication: Parallel strong orientation of an undirected graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q789182)