Efficient parallel algorithms for graph problems (Q1262781): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q391386 |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Timothy R. S. Walsh / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4091421 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finding Minimum Spanning Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4195963 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4057549 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel Prefix Computation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ultracomputers / rank | |||
Normal rank |
Latest revision as of 11:41, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient parallel algorithms for graph problems |
scientific article |
Statements
Efficient parallel algorithms for graph problems (English)
0 references
1990
0 references
From the abstract (with some additions in parentheses): We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists (computing all the products of the prefixes of \(a_ 0\circ a_ 1\circ...\circ a_ n\), where \(\circ\) is any associative operation [\textit{C. P. Kruskal}, \textit{L. Rudolph} and \textit{M. Snir}, The power of parallel prefix, IEEE Trans. Comput. 34, 965-968 (1985)]), we develop parallel algorithms that efficiently solve various computations on trees (tree-recursion and tree-traversal) and ``unicycular graphs'' (connected digraphs in which each node has in-degree one - such a graph is converted into a forest with the same connected compontents). Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems (biconnected components, and the conversion of a graph from edge-list to adjacency-list representation: the latter is also applied to compute the product of mappings). All of the graph algorithms achieve linear speedup (time inversely proportional to the number of processors) for all but the sparsest graphs (number of edges proportional to number of vertices).
0 references
EREW
0 references
linear speedup
0 references
graph algorithms
0 references
tree computation
0 references
radix sort
0 references
parallel algorithms
0 references
connected components
0 references
spanning trees
0 references
minimum spanning trees
0 references
biconnected components
0 references
0 references