A Comparison of Data-Parallel Algorithms for Connected Components

Abstract

This paper presents a pragmatic comparison of three parallel algorithms for finding connected components. together with optimizations on these algorithms. Those being compared are two similar algorithms by Awerbuch and Shiloach 2 and by Shiloach and Vishkin 19 and a randomized contraction algorithm by Blelloch 7, based on algorithms by Reif 18 and Phillips 17. Major improvements are given for the first two which significantly reduces the super- linear component of their work complexity. An improvement is also given for randomized algorithm. and this algorithm, and this to be the fastest of those tested. These comparisons are presented with NESL data-parallel code is executed on a Connection Machine 2.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 18, 1993
Accession Number
ADA270551

Entities

People

  • John Greiner

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Contracts
  • Cost Models
  • Costs
  • Diameters
  • Efficiency
  • Graph Theory
  • Iterations
  • Language
  • Optimization
  • Sequences
  • Test Methods
  • Three Dimensional
  • Two Dimensional
  • Unmanned Vehicles

Readers

  • Parallel and Distributed Computing.