|
Abstract : |
We describe efficient deterministic techniques for breaking symmetry in parallel. These techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to 3-color a rooted tree in O(lg n) time on an EREW PRAM using a linear number of processors. We use these techniques to construct fast linear processor algorithms for several problems, including (\Delta + 1)-coloring constantdegree graphs and 5-coloring planar graphs. We also prove lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs. 1, |
