A processor efficient MIS algorithm on random graphs

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

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)157-163
Number of pages7
JournalInformation Processing Letters
Issue number3
Publication statusPublished - 1994 Feb 11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'A processor efficient MIS algorithm on random graphs'. Together they form a unique fingerprint.

Cite this