A processor efficient MIS algorithm on random graphs

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

doi:10.1016/0020-0190(94)90094-9

A processor efficient MIS algorithm on random graphs

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

College of Computing

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

1 Citation (Scopus)

Abstract

In this paper we present a randomized parallel algorithm for finding a maximal independent set in a random graph with n vertices in which the edges are chosen with probability p such that 2 (n-1)≤p<1. The algorithm has O(log²n) expected time using only O(n) processors on the EREW PRAM model.

Original language	English
Pages (from-to)	157-163
Number of pages	7
Journal	Information Processing Letters
Volume	49
Issue number	3
DOIs	https://doi.org/10.1016/0020-0190(94)90094-9
Publication status	Published - 1994 Feb 11

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(94)90094-9

Cite this

@article{414638cc55f34d0a8b7bf97a9f5a3923,

title = "A processor efficient MIS algorithm on random graphs",

abstract = "In this paper we present a randomized parallel algorithm for finding a maximal independent set in a random graph with n vertices in which the edges are chosen with probability p such that 2 (n-1)≤p<1. The algorithm has O(log2n) expected time using only O(n) processors on the EREW PRAM model.",

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

year = "1994",

month = feb,

day = "11",

doi = "10.1016/0020-0190(94)90094-9",

language = "English",

volume = "49",

pages = "157--163",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - A processor efficient MIS algorithm on random graphs

AU - Yang, S. B.

AU - Dhall, S. K.

AU - Lakshmivarahan, S.

PY - 1994/2/11

Y1 - 1994/2/11

N2 - In this paper we present a randomized parallel algorithm for finding a maximal independent set in a random graph with n vertices in which the edges are chosen with probability p such that 2 (n-1)≤p<1. The algorithm has O(log2n) expected time using only O(n) processors on the EREW PRAM model.

AB - In this paper we present a randomized parallel algorithm for finding a maximal independent set in a random graph with n vertices in which the edges are chosen with probability p such that 2 (n-1)≤p<1. The algorithm has O(log2n) expected time using only O(n) processors on the EREW PRAM model.

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

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

U2 - 10.1016/0020-0190(94)90094-9

DO - 10.1016/0020-0190(94)90094-9

M3 - Article

AN - SCOPUS:0028378138

SN - 0020-0190

VL - 49

SP - 157

EP - 163

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

A processor efficient MIS algorithm on random graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this