Communication-Efficient Parallel Graph Algorithms.

Abstract

Communication bandwidth is a resource ignored by most parallel random-access machine (PRAM) models. This paper shows that many graph problems can be solved in parallel, not only with polylogarithmic performance, but with efficient communication at each step of the computation. We measure the communication requirements of an algorithm in a model called the distributed random-access machine (DRAM), in which communication cost is measured in terms of the congestion of memory accesses across cuts of an underlying network. The algorithms are based on a communication-efficient variant of the tree contraction technique due to Miller and Reif. (Author)

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1986
Accession Number
ADA178286

Entities

People

  • Bruce M. Maggs
  • Charles E. Leiserson

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Bandwidth
  • Computations
  • Congestion
  • Mathematical Analysis

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.