The parallel coloring algorithm in Zoltan is based on the work of
Boman et al. for distance-1
coloring and Bozdag et al. for
distance-2 coloring. It was implemented in Zoltan by Doruk Bozdag and
Umit V. Catalyurek, Department of Biomedical Informatics, the Ohio State
University. Distance-1 coloring algorithm is an iterative data
parallel algorithm that proceeds in two-phased rounds. In the first
phase, processors concurrently color the vertices assigned to
them. Adjacent vertices colored in the same parallel step of this
phase may result in inconsistencies. In the second phase, processors
concurrently check the validity of the colors assigned to their
respective vertices and identify a set of vertices that needs to be
re-colored in the next round to resolve the detected
inconsistencies. The algorithm terminates when every vertex has been
colored correctly. To reduce communication frequency, the coloring
phase is further decomposed into computation and communication
sub-phases. In a communication sub-phase processors exchange recent
color information. During a computation sub-phase, a number of
vertices determined by the SUPERSTEP_SIZE parameter, rather than a
single vertex, is colored based on currently available color
information. With an appropriate choice of a value for SUPERSTEP_SIZE,
the number of ensuing conflicts can be kept low while at the same time
preventing the runtime from being dominated by the sending of a large
number of small messages. The distance-2 graph coloring problem aims
at partitioning the vertex set of a graph into the fewest sets
consisting of vertices pairwise at distance greater than two from each
other. The algorithm is an extension of the parallel distance-1
coloring algorithm.