Processor efficient connectivity algorithm on random graphs

S. B. Yang; S. K. Dhall; S. Lakshmivarahan

Processor efficient connectivity algorithm on random graphs

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

College of Computing

Research output: Contribution to journal › Article › peer-review

Abstract

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(log²n) 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.6^k, where k is a constant.

Original language	English
Pages (from-to)	29-36
Number of pages	8
Journal	Parallel Processing Letters
Volume	4
Issue number	1-2
Publication status	Published - 1994 Jun

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture

Cite this

@article{78735b977940483b871a71296cbe816b,

title = "Processor efficient connectivity algorithm on random graphs",

abstract = "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.",

author = "Yang, {S. B.} and Dhall, {S. K.} and S. Lakshmivarahan",

year = "1994",

month = jun,

language = "English",

volume = "4",

pages = "29--36",

journal = "Parallel Processing Letters",

issn = "0219-6264",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "1-2",

}

TY - JOUR

T1 - Processor efficient connectivity algorithm on random graphs

AU - Yang, S. B.

AU - Dhall, S. K.

AU - Lakshmivarahan, S.

PY - 1994/6

Y1 - 1994/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028450249&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028450249&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0028450249

SN - 0219-6264

VL - 4

SP - 29

EP - 36

JO - Parallel Processing Letters

JF - Parallel Processing Letters

IS - 1-2

ER -

Processor efficient connectivity algorithm on random graphs

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this