EFFICIENT PARALLEL ALGORITHMS FOR GRAPH PROBLEMS.

Clyde P. Kruskal, Larry Rudolph, Marc Snir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Efficient techniques for manipulating linked structures in parallel are presented. These techniques work on the EREW machine, which is the weakest shared memory machine. The authors develop algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of these algorithms achieve linear speedup for all but the sparsest graphs. A parallel radix sort algorithm is also presented that is optimal for keys taken from a small range.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel Processing
EditorsKai Hwang, Steven M. Jacobs, Earl E. Swartzlander
PublisherIEEE
Pages869-876
Number of pages8
ISBN (Print)0818607246
StatePublished - Dec 1 1986
Externally publishedYes

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'EFFICIENT PARALLEL ALGORITHMS FOR GRAPH PROBLEMS.'. Together they form a unique fingerprint.

Cite this