A randomized BSP/CGM algorithm for the maximal independent set problem

This paper presents a randomized parallel algorithm for the Maximal Independent Set problem. Our algorithm uses a BSP-like computer with p processors and requires that n+m/p=/spl Omega/(p) for a graph with 72 vertices and m edges. Under this scalability assumption, and after a preprocessing phase, i...

Full description

Saved in:
Bibliographic Details
Main Authors: Ferreira, A., Schabanel, N.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Communication networks
Computational modeling
Concurrent computing
Nominations and elections
Parallel algorithms
Phase change random access memory
Sorting
System recovery
User-generated content
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a randomized parallel algorithm for the Maximal Independent Set problem. Our algorithm uses a BSP-like computer with p processors and requires that n+m/p=/spl Omega/(p) for a graph with 72 vertices and m edges. Under this scalability assumption, and after a preprocessing phase, it computes a maximal independent set after O(log p) communication rounds, with high probability, each round requiring linear computation time O(n+p/p). The preprocessing phase is deterministic and important in order to ensure that degree computations can be implemented efficiently. For this, we give an optimal parallel BSP/CGM algorithm to the p-quantiles search problem, which runs in O(m log p/p) time and a constant number of communication rounds, and could be of interest in its own right, as shown in the text.
ISSN:1087-4089
2375-527X
DOI:10.1109/ISPAN.1999.778953