Optimal Parallel Algorithms for Interger Sorting and Graph Connectivity.

Abstract

This document gives new parallel algorithms for integer sorting and undirected graph connectivity problems such as connected components and spanning forest. These algorithms cost only logarithmic time and are the first known that are optimal: the product of their time and processor bounds are bounded by a linear function of the input size. All previous known parallel algorithms for these problems required at least a linear number of processors to achieve logarithmic time bounds, and hence were nonoptimal by at least a logarithmic factor. The author assumes a parallel random access machine (RAM) model which allows both concurrent writes and concurrent reads of global memory. The algorithms are randomized; each processor is allowed an independent random number generator; however our stated resource bounds hold for worst case input with overwhelming likelihood as the input size grows. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1985
Accession Number
ADA161791

Entities

People

  • John Reif

Organizations

  • Harvard University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Binomials
  • Classification
  • Collapse
  • Computations
  • Computer Science
  • Discrete Distribution
  • New York
  • Parallel Computing
  • Permutations
  • Probability
  • Probability Distributions
  • Random Variables
  • Sampling
  • Security
  • Statistical Sampling
  • Theorems

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research
  • Parallel and Distributed Computing.