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.