Optimal Parallel Algorithms for Graph Connectivity.

Abstract

We give a new randomized parallel RAM algorithm for finding a spanning forest of an undirected graph in logarithmic time. These time bounds hold with arbitrary high probability for any input graph (i.e., we do not assume random input; these bounds hold for the worst case input graph). This result assumes a parallel RAM model which allows both concurrent writes and concurrent reads. Furthermore, we show that if the graph is not very sparse (i.e., if the number of edges is at least a logarithmic squared factor more than the number of vertices) than we can achieve a linear processor time product (even for logarithmic time bounds) for finding a spanning tree--which is optimal for the parallel RAM model. Furthermore, we can also achieve a linear processor, time product for even sparser graphs with only slight time increase. Keywords include: graph connectivity, parallel algorithms, optimal algorithms, randomized algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1984
Accession Number
ADA152095

Entities

People

  • J. H. Reif

Organizations

  • Harvard University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Binomials
  • Computations
  • Computer Science
  • Computers
  • Iterations
  • Language
  • Military Research
  • New York
  • Parallel Computing
  • Probability
  • Random Variables
  • Security
  • Simulations
  • Universities

Fields of Study

  • Computer science

Readers

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