Parallel strong orientation of an undirected graph (Q789182)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Parallel strong orientation of an undirected graph |
scientific article; zbMATH DE number 3845068
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Parallel strong orientation of an undirected graph |
scientific article; zbMATH DE number 3845068 |
Statements
Parallel strong orientation of an undirected graph (English)
0 references
1984
0 references
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).
0 references
parallel computation
0 references
graph algorithms
0 references
parallel algorithm
0 references
shared memory model
0 references
strong orientation
0 references
