Affordable Access

Publisher Website

Connected Components inO(log3/2 n) Parallel Time for the CREW PRAM

Authors
Journal
Journal of Computer and System Sciences
0022-0000
Publisher
Elsevier
Publication Date
Volume
54
Issue
2
Identifiers
DOI: 10.1006/jcss.1997.1291
Disciplines
  • Computer Science

Abstract

Abstract Finding the connected components of an undirected graph G=( V, E) on n=| V| vertices and m=| E| edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs in O(log 2 n) time using n 2/log 2 nprocessors. For the CRCW PRAM model, in which concurrent writing is permitted, the best known algorithm runs in O(log n) time using slightly more than ( n+ m)/log nprocessors. Simulating this algorithm on the weaker CREW model increases its running time to O(log 2 n). We present here a simple algorithm that runs in O(log 3/2 n) time using n+ mCREW processors. Finding an o(log 2 n) parallel connectivity algorithm for this model was an open problem for many years.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Finding Connected Components inO(lognlog logn) Tim...

on Journal of Algorithms Jan 01, 1995

AnO(n2logn) parallel max-flow algorithm

on Journal of Algorithms Jan 01, 1982

Energetic and structural analysis of N2H4BH3inorga...

on International Journal of Hydro... May 30, 2013

Estimation of night-time N2O5concentrations from a...

on Atmospheric Environment (1967) Jan 01, 1986
More articles like this..