Efficient Parallel Algorithms for (5+1)-Coloring and Maximal Independent Set Problems.
Abstract
We described an efficient technique for breaking symmetry in parallel. The technique works especially well on rooted trees and on graphs with a small maximum degree. In particular, we can find a maximal independent set on a constant-degree graph in O(lg*n) time on an EREW PRAM using a linear number of processors. We show how to apply this technique to construct more efficient parallel algorithms for several problems, including coloring of planar graphs and (delta + 1)-coloring of constant-degree graphs. We also prove lower bounds for two related problems. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1987
- Accession Number
- ADA178287
Entities
People
- Andrew V. Goldberg
- Serge A. Plotkin
Organizations
- Massachusetts Institute of Technology