Theoretical and Experimental Analyses of Parallel Combinatorial Algorithms

Abstract

This thesis investigates parallel algorithms for a small, but representative, subclass of graph and matrix problems. In some cases, we develop new algorithms which we analyze for theoretical efficiency. In other cases, we modify and implement existing algorithms which we analyze for practical efficiency. We show how n-node, e-edge graphs can be contracted in a manner similar to the parallel tree contraction algorithm due to Miller and Reif. We give an O((n+e)/lgn)-processor deterministic algorithm that contracts a graph in O(lg squared n) time in the EREW PRAM model.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1989
Accession Number
ADA216407

Entities

People

  • Cynthia A. Phillips

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Cyber
  • Energy and Power Technologies
  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Communication Channels
  • Communication Systems
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Electrical Engineering
  • Engineering
  • Language
  • Linear Programming
  • Operations Research
  • Parallel Computing
  • Probability
  • Simplex Method
  • Two Dimensional

Fields of Study

  • Computer science

Readers

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