## Abstract

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_{max}) processors is O(log n), where d_{max} denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log^{2}n). Previously, an O(log^{4}n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log^{2}n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.

Original language | English (US) |
---|---|

Pages (from-to) | 567-583 |

Number of pages | 17 |

Journal | Journal of Algorithms |

Volume | 7 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1986 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics