Name
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) less than or equal to p < 1. The algorithm has O(log(2)n) expected time using only O(n) processors on the EREW PRAM model. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0020-0190(94)90094-9 | Inf. Process. Lett. |
Keywords | Field | DocType |
random graph,processor efficient mis algorithm | Random regular graph,Discrete mathematics,Combinatorics,Random graph,Algorithmics,Parallel algorithm,Analysis of algorithms,Algorithm,Hopcroft–Karp algorithm,Independent set,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
49 | 3 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. B. Yang | 1 | 0 | 1.35 |
| Dhall | 2 | 271 | 80.48 |
| S. Lakshmivarahan | 3 | 412 | 66.03 |