Processor efficient connectivity algorithm on random graphs

S. B. Yang, S. K. Dhall, S. Lakshmivarahan

Research output: Contribution to journalArticlepeer-review


In this paper we present a randomized parallel algorithm for finding the connected components of a random input graph with n vertices in which the edges are chosen with probability p such that 2/n-1≤p<1, n>3. The algorithm has O(log2n) expected time using only O(n) processors on the EREW PRAM model. The probability that time output of our algorithm is correct is at least 1 - 0.6k, where k is a constant.

Original languageEnglish
Pages (from-to)29-36
Number of pages8
JournalParallel Processing Letters
Issue number1-2
Publication statusPublished - 1994 Jun

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Processor efficient connectivity algorithm on random graphs'. Together they form a unique fingerprint.

Cite this