Parallel strong orientation of an undirected graph
type: Item
instance of: scholarly article
title: Parallel strong orientation of an undirected graph
zbMATH Open document ID: 0532.68065
DOI: 10.1016/0020-0190(84)90072-3
author: Mikhail J. Atallah
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi
review text: 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).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 3845068
zbMATH Keywords: parallel computation
zbMATH Keywords: graph algorithms
zbMATH Keywords: parallel algorithm
zbMATH Keywords: shared memory model
zbMATH Keywords: strong orientation
MaRDI profile type: Publication
OpenAlex ID: W2076461794
cites work: Q4146249
cites work: Parallel Algorithms in Graph Theory: Planarity Testing
cites work: New Parallel-Sorting Schemes
cites work: Fast, Efficient Parallel Algorithms for Some Graph Problems
description: scientific article; zbMATH DE number 3845068