A Parallel Distance-2 Graph Coloring Algorithm
for Distributed Memory Computers
Doruk Bozdağ 1 , Umit Catalyurek 1 , Assefaw H. Gebremedhin 2 , Fredrik Manne 3 ,Erik G. Boman 4 , and Füsun Özgüner 1
1

Ohio State University, USA{bozdagd, ozguner}@ece.osu.edu, umit@bmi.osu.edu
2
Old Dominion University, USA
assefaw@cs.odu.edu
3
University of Bergen, Norway
Fredrik.Manne@ii.uib.no4
Sandia National Laboratories, USA
egboman@sandia.gov

Abstract. The distance-2 graph coloring problem aims at partitioning the vertex set of a graph into the fewest sets consisting of vertices pairwise at distancegreater than two from each other. Application examples include numerical optimization and channel assignment. We present the first distributed-memory heuristic algorithm for this NP-hard problem. Parallel speedup is achieved throughgraph partitioning, speculative (iterative) coloring, and a BSP-like organization ofcomputation. Experimental results show that the algorithm is scalable, and compares favorably with an alternative approach—solving the problem on a graph G
by first constructing the square graph G2 and then applying a parallel distance-1
coloring algorithm on G2 .

1 Introduction
An archetypal problem in the efficient computation of sparse Jacobian and Hessian
matrices is the distance-2 (D2) vertex coloring problem in an appropriate graph [1]. D2
coloring also finds applications in channel assignment [2] and facility location problems[3]. It is closely related to a strong coloring of a hypergraph which in turn models
problems that arise in the design of multifiber WDM networks [4]. The D2 coloring
problem is known to be NP-hard [5].
In many parallel applications where a graph coloring is required, the graph is already distributed among processors. Under such circumstances, gathering the graph on
one processor to perform the coloring may not be feasible due to memory constraints.
Moreover, in some parallel applications the coloring needs to be performed repeatedlyThis work was supported in part by NSF grants ACI-0203722, ACI-0203846, ANI-0330612,
CCF-0342615, CNS-0426241, NIH NIBIB BISTI P20EB000591, Ohio Board of Regents
BRTTC BRTT02-0003, Ohio Supercomputing Center PAS0052, and SNL Doc.No: 283793.
Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin company, for the U.S. DOE’s National Nuclear Security Administration under contract DE-AC0494AL85000.

L.T. Yang et al. (Eds.): HPCC 2005, LNCS 3726, pp. 796–806, 2005.
c Springer-Verlag Berlin Heidelberg 2005
A Parallel Distance-2 Graph Coloring Algorithm

797

due to changes in the structure of the graph. Here, the coloring may take up a substantial
amount of overall computation time unless a scalable algorithm is used.
A number of papers dealing with the design of efficient parallel distance-1 (D1)coloring algorithms have appeared [6,7,8,9]. For D2 coloring we are not aware of any
work other than [10] where an algorithm for shared memory computers was presented.
In this paper, we present an efficient parallel D2 coloring algorithm suitable for distributed memory computers. The algorithm is an extension of the parallel D1 coloringalgorithm presented in [6]. The latter 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 validityof 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. During a computation sub-phase, a group of vertices, rather than a single
vertex, is colored based on currently available color information. In a communication
sub-phase processors exchange recent color information.
The key issue in extending this approach to the D2 coloring case is devising anefficient means of information exchange between processors hosting a pair of vertices
that are two edges away from each other. We use a scheme in which the host processor ofa vertex v is responsible for (i) coloring v , (ii) relaying color information to processorsthat store the D1 neighbors of v , and (iii) detecting inconsistencies that involve the D1neighbors of v .
Our parallel D2 coloring algorithm has been implemented using MPI. Results fromexperiments performed on a 32-node PC cluster using a number of real-world as wellas random graphs show that the algorithm is efficient and scalable. We have also compared our D2 coloring algorithm on a given graph G with the parallel D1 coloringalgorithm from [6] applied to the square graph G2 . These results in general show that
our algorithm scales better and uses less memory and storage.
In the sequel, we discuss preliminary concepts in Section 2; present our algorithm
in Section 3; report experimental results in Section 4 and conclude in Section 5.

2 Distance-2 Graph and Hypergraph Coloring
Two distinct vertices in a graph G = (V, E) are distance- k neighbors if the shortest pathconnecting them consists of at most k edges. A distance- k coloring of G = (V, E) is amapping C : V → {1, 2, . . . , q} such that C(v) = C(w) whenever vertices v and w
are distance- k neighbors. The associated optimization problem aims at minimizing q .
A distance-k coloring of a graph G = (V, E) is equivalent to a D1 coloring of the k th
power graph G k = (V, F ) where (v, w) ∈ F whenever vertices v and w are distance- kneighbors in G . We denote the set of distance-k neighbors of vertex v by Nk (v), and theset Nk (v)∪{v} by Nk [v]. For simplicity, we drop the subscript in the case where k = 1 .
Let A be a symmetric matrix with nonzero diagonal elements and Ga (A) = (V, E)
be the adjacency graph of A, where V corresponds to the columns of A. As illustrated

798

D. Bozdağ et al.
a 11 00
0 a 150 a 22 a 23 00
0 a 32 a 33 a 34 a 35
0
0 a 43 a 44 a 45
a 51 0 a 53 a 54 a 55

a1

A

a1

a3

a5

A

a 11 a 12 0
0 a 15a 21 a 22 000a 31 00 a 34 00
0 a 43 a 44 a 45

a2

c1

a4

Ga

Ga

c3
c4

a3

a5

a4

c2

c5

a2

2

V1
r1
r2
r3
r4

V2
c1
c2
a3
c4
c

c1

c2
c3

c5
c4

5

H

Gb

2

G b [V2]

Fig. 1. Equivalence among structurally orthogonal column partition of A , D2 coloring of G(A)and D1 coloring of G 2 (A) . Top: symmetric case. Bottom: non-symmetric case (also shows equivalence with strong coloring of hypergraph H ).

in the upper row of Figure 1, a partitioning of the columns of A into groups of structurally orthogonal columns is equivalent to a D2 coloring of Ga (A). (Two columns are
structurally orthogonal if they do not have nonzero entries in the same row.) The rightmost subfigure in Figure 1 shows the equivalent D1 coloring in the square graph Ga2 .
Now let A be non-symmetric. The bipartite graph of A is the graph Gb = (V1 , V2 , E)
where V1 is the row vertex set, V2 is the column vertex set, and there exits an edge between row vertex ri and column vertex cj whenever aij = 0 . As the lower row of
Figure 1 illustrates, a partitioning of the columns of A into groups of structurally orthogonal columns is equivalent to a partial D2 coloring of Gb (A) on V2 . The right mostsubfigure shows the equivalent D1 coloring of Gb2 [V2 ], the subgraph of the square graph
Gb2 induced by V2 .
D2 coloring of a bipartite graph is also related to a variant of hypergraph coloring.
A hypergraph H = (V, E) consists of a vertex set V and a collection E of subsets of V
called hyperedges. A strong hypergraph coloring is a mapping C : V → {1, 2, . . . , q}such that C(v) = C(v) whenever {v, w} ⊆ e ∈ E . As Figure 1 illustrates, a strong
coloring of a hypergraph is equivalent to a partial D2 coloring of its hyperedge-vertex
incidence bipartite graph. For further discussion on the equivalence among matrix partitioning, D2 graph coloring and hypergraph coloring as well as their relationships tocomputation of Jacobians and Hessians, see [1].

3 Parallel Distance-2 Coloring
In this section we describe our new parallel D2 coloring algorithm for a general graph
G = (V, E). Initially, the input graph is assumed to be distributed among p processors.
The set Vi of vertices in the partition { V1 , . . . , Vp } of V is assigned to and colored byprocessor Pi ; we say that Pi owns Vi . Pi also stores the adjacency list of its vertices
and the IDs of the processors owning them. This classifies V into interior and boundary

A Parallel Distance-2 Graph Coloring Algorithm

799

Algorithm 1 An iterative parallel distance-2 coloring algorithm
procedure PARALLEL C OLORING( G = (V, E ), s )Initial data distribution: G is divided into p subgraphs G1 = (V1 , E1 ), . . . , Gp =(Vp , Ep ) where V1 , . . . , Vp is a partition of the set V and Ei = {(v, w) : v ∈Vi , (v, w) ∈ E } . Processor Pi owns the vertex set Vi , and stores the edge set Ei andthe ID’s of the processors owning the other endpoints of Ei .
on each processor Pi , i ∈ P = {1, . . . , p}Color interior vertices in Vi
Ui ← boundary vertices in Vi Ui is to be iteratively colored by Pi
while ∃j ∈ P, Uj = ∅ do
 Wi is examined for conflicts by Pi
Wi ← COLOR( Gi , Ui , s )Ui ← D ETECT C ONFLICTS( Gi, Wi )vertices. All D1 neighbors of an interior vertex are owned by the same processor as
itself. A boundary vertex has at least one D1 neighbor owned by a different processor.
Clearly, any pair of interior vertices, that are assigned to different processors, cansafely be colored concurrently. This is not true for a pair containing a boundary vertex.
In particular, if such a pair is colored at the same parallel superstep, then the partners
may receive the same color and result in a conflict. However, if we enforce that interiorvertices be colored before or after boundary vertices, then a conflict can only occur
for pairs of boundary vertices. Thus, the presented algorithm is concerned with parallel
coloring of boundary vertices.
The main idea in our algorithm is to color boundary vertices concurrently in a speculative manner and then detect and rectify conflicts that may have arisen. The algorithm
is iterative—it proceeds in rounds. Each round consists of a tentative coloring and aconflict detection phase. Both of these phases are performed in parallel. The latter phasedetects conflicts in a current coloring and accumulates a list of vertices to be recoloredin the next round. Given a pair of vertices involved in a conflict, only one of them needs
to be recolored to resolve the conflict; the choice is done randomly. The algorithm terminates when there are no more vertices to be colored. The high-level structure of thealgorithm is outlined in Algorithm 1.
Notice the termination condition of the while-loop. Even if a processor Pi currently
has no vertices to color ( Ui = ∅ ), it could still be active since other processors may require color information from Pi . Furthermore, Pi may participate in detecting conflicts
on other processors.
For every path v, w, x, the host processor for vertex w is responsible for detecting
D2 conflicts that involve vertices v and x as well as D1 conflicts involving w and
its adjacent vertices N (w). The set Wi in Algorithm 1 contains the current set ofvertices residing on processor Pi that will be examined for detecting these conflicts. Wi
includes both ‘middle’ vertices, and vertices from Ui . The discussion of the routines
COLOR and D ETECT C ONFLICTS in Sections 3.1 and 3.2 will clarify these points.
3.1 The Tentative Coloring Phase
The tentative coloring phase is organized as a sequence of supersteps. In each superstep,
each processor colors s vertices sequentially, and sends the colors of these vertices to800

D. Bozdağ et al.

Pk
Pi

Pi
v

(i)

Pj
Pi

v

Pj
v

(ii)

(iii)

Fig. 2. Distribution scenarios of the distance-2 neighbors of vertex v across processors

processors owning their D1 neighbors. To perform the coloring, a processor first gathers
information from other processors to build a (partial) list of forbidden colors for eachof its boundary vertices scheduled to be colored in the current superstep. Such a list
for a vertex v consists of the colors used by its already colored D2 neighbors. The
colors of the off-processor vertices in N (v) colored in previous supersteps are easily
available since the host processor of v has already received and stored them. We referto such and on-processor colors as local. However, the colors used by vertices exactly
two edges away from v may have to be obtained from another processor.
Figure 2 illustrates the three scenarios in which the vertices on a path v, w, x may be
distributed among processors. Case (i) corresponds to the situation where both w andx are owned by Pi . Case (ii) shows the situation where w is owned by Pi and x is
owned by Pj , j = i . In these two cases, the color of w is local to Pi . Case (iii) shows
the situation where w is owned by Pj , and vertices v and x do not have a common D1neighbor owned by Pi . Vertex x may be owned by any one of the three processors Pi ,Pj , or Pk , i = j = k . In case (iii), the color of x is not local to Pi and needs to be
relayed through Pj which is capable of detecting the situation. In particular, Pj builds
and sends a list of forbidden colors for each vertex owned by Pi that Pi cannot accessdirectly. Since Pj does not know the internal structure of the vertices in Pi , it includes
the color of every x in the list of forbidden colors for v for each path v, w, x where w
is owned by Pj .
At the beginning of the algorithm, each processor sends a coloring-schedule of its
boundary vertices to neighboring processors. In this way, each processor will know theD2 color information it needs to send in each superstep. Note that it is only necessary tosend information regarding D1 neighbors of a vertex owned by another processor. Eachprocessor then computes a list Xi of vertices on neighboring processors for which it
must supply color information. With the knowledge of Xi , processor Pi can now be“pro-active” in building and sending lists of relevant color information. When a processor receives the partial lists of forbidden colors from all of its neighboring processors, itmerges these lists with local color information to determine a complete list of forbidden
colors for its vertices scheduled to be colored in the current superstep. Using this information, a processor then speculatively colors these vertices and sends the new color
information to processors owning D1 neighbors.
In addition to coloring vertices in the current set Ui , a processor also computes a list
Wi of vertices that it needs to examine in the conflict detection phase. Two vertices are
involved in a conflict only if they are colored in the same superstep. Thus Wi consists

A Parallel Distance-2 Graph Coloring Algorithm801

of (i) every vertex that has at least two neighbors on different processors that are coloredin the same superstep, and (ii) every vertex v in Ui that has at least one neighbor on aprocessor Pj , j = i , colored in the same superstep as v . The tentative coloring routine
sketched so far is outlined with more details in Algorithm 2.
The set Wi is efficiently determined in the following manner. The vertices in Xi ∪Ui are traversed a superstep at a time. For each superstep, first, each vertex in Ui andits neighboring boundary vertices are marked. Then for each vertex v ∈ Xi the vertices
in N (v) owned by processor Pi are marked. If this causes some vertex to be marked
twice in the same superstep, then the vertex is added to Wi . The combined sequential
work carried out by Pi and its neighboring processors to perform the coloring of Ui
is O(Σv∈Ui |h(v)|) where h(v) is the graph induced by the edges incident on N [v].
Summing over all processors, the total work involved in coloring the vertices in U =∪Ui is O(Σv∈U |h(v)|) which is equivalent to the complexity of a sequential algorithm.
Algorithm 2 Speculative coloring
1: function C OLOR( Gi , Ui , s )2:Partition Ui into i subsets Ui,1 , Ui,2 , . . . , Ui,i , each of size s , and send the schedule
to relevant
processorsii Uj,k: vertices received by Pi to be colored by Pj in step k3:
Xi ← j,k Uj,k4:
for each v ∈ Ui ∪ Xi do
5:C(v) ← 0 (re)initialize colors
 Wi is used for detecting conflicts
6:
Wi ← ∅
7:for each v ∈ Vi s.t v has at least two neighbors in Xi ∪ Ui on different processors,
both colored in the same superstep do
8:
Wi ← Wi ∪ {v}
9:for each v ∈ Ui s.t v has at least one neighbor in Xi that is colored in the same
superstep as v do
10:
Wi ← Wi ∪ {v} each ki corresponds to a superstep
11:
for ki ← 1 to i do Pj is not in its last superstep
12:
for each neighboring Pj where kj < j do
13:
Build and send lists of forbidden colors to Pj for relevant vertices in Uj,kj +1
14:
Receive and merge lists of forbidden colors for relevant vertices in Ui,ki
15:
Update lists of forbidden colors with local color information
16:
for each v ∈ Ui,ki do
17:
C(v) ← c s.t. c = 0 is the smallest permissible color for v
18:
Send colors of relevant vertices in Ui,ki to neighboring processors
19:
while ∃j ∈ P , s.t. Pj is a neighbor of Pi and kj ≤ lj do
20:
Receive color information for superstep kj from Pj
21:
if kj < lj then22:
Build and send list of forbidden colors to Pj for relevant vertices in Uj,kj +1
23:
return Wi

For each v ∈ Ui , processor Pi receives the colors of vertices exactly two edges
from v from processors hosting vertices in N (v). Meanwhile, such processors receive
the color of v from Pi . The only time a color might be sent to Pi more than once iswhen there exists a triangle v, w, x where w is owned by Pj , x is owned by Pk , and802

D. Bozdağ et al.

i , j and k are all different. In such a case, both Pj and Pk would send the color of x
to Pi . In any case, the overall size of communicated data is bounded by Σv∈∪Ui |h(v)|.
The discussion above implies that a partitioning of G among processors where thenumber of boundary vertices is small relative to the number of interior vertices on eachprocessor is highly desirable as it reduces communication cost.
3.2 The Conflict Detection Phase
A conflict involving a pair of adjacent vertices is detected by both processors owningthese vertices. A conflict involving a pair of vertices exactly two edges apart is detectedby the processor owning the middle vertex. To resolve a conflict, one of the involved
vertices is randomly chosen to be recolored in the next round. Algorithm 3 outlines theparallel conflict detection phase D ETECT C ONFLICTS executed on each processor Pi .
This routine returns a set of vertices to be colored in the next round by Pi .
Each processor Pi accumulates and sends a list Ri,j of vertices to be recoloredby each Pj in the next round. Pi is responsible for recoloring vertices in Ri,i andtherefore adds received notifications Rj,i from each neighboring processor Pj to Ri,i .
To efficiently determine the subset of Wi that needs to be recolored, we use twocolor-indexed tables seen[] and where[]. The assignment seen[c] = w for a vertex
w ∈ Wi is effected if at least one vertex in N[w] of color c has already been encountered. The entry where[c] stores the vertex with the lowest random value among these.
Initially both seen[C(w)] and where[C(w)] are set to w . This ensures that any conflict involving w and a vertex in N (w) will be discovered. For each neighbor of w , a
Algorithm 3 Conflict Detection
1: function D ETECT C ONFLICTS( Gi, Wi )
 Ri,j is a set of vertices Pi notifies Pj to recolor
2:
Ri,j ← ∅ for each j ∈ P
3:for each vertex w ∈ Wi do
4:seen[C(w)] ← w
5:where[C(w)] ← w
6:for each x ∈ N (w) do
7:
if seen[C(x)] = w then8:v ← where[C(x)]9:
if r(v) ≤ r(x) then r(x) is a random number associated with x I(u) is ID of processor owning u
10:
Ri,I(x) ← Ri,I(x) ∪ {x}
11:
else
12:
Ri,I(v) ← Ri,I(v) ∪ {v}13:where[C(x)] ← x
14:
else
15:
seen[C(x)] ← w
16:where[C(x)] ← w
17:for each j = i ∈ P do
18:
send Ri,j to processor Pj
19:
for each j = i ∈ P do
20:
receive Rj,i from processor Pj
21:
Ri,i ← Ri,i ∪ Rj,i22:
return Ri,i

A Parallel Distance-2 Graph Coloring Algorithm803

check on whether its color has already been seen is done. If the check turns positive,the vertex that needs to be recolored is determined based on a comparison of random
values and the table where is updated accordingly (Lines 3–16).
Note that in Line 6, it is sufficient to only check for conflicts using vertices that areboth in N (w) and in either Ui or Xi . However, determining which vertices in N (w)this applies to takes more time than testing for a conflict. Also, it is not necessary to
notify a neighboring processor on the detection of a conflict involving adjacent vertices
as the conflict will also be discovered by the other processor.

4 Experimental Results
We carried out experiments on a 32-node PC cluster equipped with dual 2.4 GHz IntelP4 Xeon CPUs with 4 GB of memory. The nodes are interconnected via a switched
10Gbps Infiniband network. Our test set consists of 21 graphs from molecular dynamics
and finite element applications [11,7,12,13]. We report average results for each class ofgraphs, instead of individual graphs. Each result is in turn an average of 5 runs.
The left half of Table 4 displays the structural properties of the test graphs. The firstpart of the right half lists the number of colors and the runtime in milliseconds used by a
Table 1. Structural properties of the test graphs classified according to application area (left).
Performance results (right). Sources: MD [13]; FE [7]; CA, SH [11]; ST, AU, CE [12].
D2
D1 on G 2 (norm.)
app name|V ||E|
Degreetime
conv. color.
max avg time colors (norm.) colors ×|E| time time
popc-br-4 24,916
255,047 43 20
3.3 21
20.6
75
4.7 33.0 4.8
MD er-gre-4
36,573451,355 42 25
5.5 1923.2
66
5.0 34.6 5.1
apoa1-4
92,224 1,131,436 43 25 16.5 20
18.1
73
5.0 28.5 4.3
144
144,649 1,074,393 26 15 44.3 12
20.5
41
4.8 25.8 4.0
FE 598a110,971
741,934 26 13 35.0 11
20.9
38
4.7 28.3 4.0
auto
448,695 3,314,611 37 15 248.9 13
16.1
42
4.9 16.6 4.5
bmw3 2 227,362 5,530,634 335 49 53.3 48
42.7 336 3.2 35.7 3.0
CA bmw7st1 141,347 3,599,160 434 51 34.4 54
43.8 435 3.3 35.6 3.0
inline1 503,712 18,156,315 842 72 179.5 51
70.5 843 7.0 63.8 6.2
pwtk
217,918 5,708,253 179 52 50.7 48
45.5 180 2.9 34.8 2.7
ST nasasrb
54,870 1,311,227 275 48 11.7 41
42.8 276 3.2 35.5 3.2
ct20stif
52,329 1,323,067 206 51 12.5 49
46.0 210 3.8 37.7 3.5
hood
220,542 5,273,947 76 48 58.5 42
35.8 103 3.2 29.2 2.7
AU ldoor
952,203 22,785,136 76 48 249.7 42
35.8 112 3.2 29.0 2.7
msdoor 415,863 9,912,536 76 48 106.2 42
36.9 105 3.2 29.8 2.7
pkustk10 80,676 2,114,154 89 52 20.1 42
43.6 126 2.9 33.0 2.7
CE pkustk11 87,804 2,565,054 131 58 23.7 66
57.6 198 4.2 45.6 3.8
pkustk13 94,893 3,260,967 299 69 29.2 57
72.5 303 6.0 62.2 6.0
shipsec1 140,874 3,836,265 101 54 34.9 48
48.5 126 3.1 37.7 8.2
SH shipsec5 179,860 4,966,618 125 55 46.4 50
48.5 140 3.2 37.2 3.0
shipsec8 114,919 3,269,240 131 57 29.1 54
52.9 150 3.5 41.2 3.4
D1

D. Bozdağ et al.

30

Speedup

25

1

FE
AU
CA
SH
ST
CE
MD

0.9
0.8

Round Time

804

20

15

10

0.7
0.6
0.5
0.4
0.3
0.2

5

0.1
0

5

10

15

20

Number of processors

25

30

0

FE

AU

CA

SH

ST

CE

MD

Graphs(a)(b)
Fig. 3. (a) Speedup while varying number of processors for s = 100 . (b) Breakdown of execution
time into rounds and coloring and conflict detection phases for p = 16 . Each bar is divided into
time spent on coloring (bottom) and time spent on conflict detection (top).

sequential D1 coloring algorithm. The second part shows timings for two different waysof sequentially achieving a D2 coloring: a direct D2 coloring on G and a D1 coloring on
G2 . The time spent on constructing G 2 from G is given under column conv. time. The
reported times have been normalized with respect to the corresponding time requiredfor performing a D1 coloring. We also list the ratio of the number of edges in G 2 to thatin G , to show the relative increase in storage requirement.
As one can see, G 2 requires a factor of nearly 3 to 7 more storage than G . D2coloring on G is in most cases slightly slower than constructing and then D1 coloringG 2 . We believe this is due to the fact that a D1 coloring on G 2 accesses memory moresequentially in comparison with a D2 coloring on G .
Figure 3(a) shows the speedup obtained in using our D2 coloring algorithm on
G while keeping the superstep size fixed at 100. For most graph classes, reasonable
speedup is obtained as the number of processors is increased. We have also conducted
experiments to investigate the impact of superstep size. We found that with the exception of extreme values, superstep size does not significantly influence speedup.
We observed that the number of conflicts increases with increasing number of processors and superstep size. Still, it stays fairly low and does not exceed 10% of the number of vertices with the exception of MD graphs with up to 32 processors for s = 100 .
The number of rounds the algorithm had to iterate was observed to be consistently low,increasing only slowly with superstep size and number of processors. This is due tothe fact that the number of initial conflicts drops rapidly between successive rounds. To
further show how the time within each round is spent we present Figure 3(b). The figure
shows the time spent on coloring boundary vertices and conflict detection in each roundfor 16 processors. All timings are normalized with respect to the time spent in the firstround, excluding the time spent on coloring interior vertices.
Figure 4(a) shows how the total time is divided into time spent on coloring interiorvertices, coloring boundary vertices, and conflict detection. All timings are normalizedwith respect to the sequential coloring time. As the number of processors increases, thetime spent on coloring boundary vertices does not change much while the time spenton coloring interior vertices decreases almost linearly. This should be seen in light of

A Parallel Distance-2 Graph Coloring Algorithm

805

1
0.9
0.5

Coloring Time

Coloring Time

0.8
0.4

0.3

0.2

0.7
0.6
0.5
0.4
0.3
0.2

0.1

0.1
0

FE

AU

CA

SH

ST

Graphs(a) Graphs in Table 4

CE

MD

0

d=10

d=20

d=30

d=40

Graphs(b) Random graphs

Fig. 4. Breakdown of execution time into time spent on coloring internal vertices (bottom), coloring boundary vertices (middle), and conflict detection (top). For each graph class, timings for
p = 2, 4, 8, 12, 16, 24, 32 are reported.

the fact that the number of boundary vertices increases as more processors are applied
whereas the coloring of interior vertices does not involve any communication.
To investigate scalability on boundary vertices, we performed experiments on random graphs. For a random graph almost every vertex becomes a boundary vertex regardless of how the graph is partitioned. We generated random graphs with 100,000 vertices
and with average degrees of 10, 20, 30, and 40. Figure 4(b) shows that the algorithm
scales fairly well and almost all the time is spent on coloring boundary vertices.
We have also evaluated D1 coloring on G 2 and experimental results (omitted due tospace constraints) indicate that this approach is less scalable and requires more storage
than the D2 coloring on G approach due to large density of G 2 . We intend to implement
parallel construction of G 2 and investigate trade-offs between these two approaches inmore detail in a future work.

5 Conclusion
We have presented an efficient parallel distance-2 coloring algorithm suitable for distributed memory computers and experimentally demonstrated its scalability. In a future
work we plan to adapt the presented algorithm to solve the closely related strong hypergraph coloring problem. This brings up the open problem of finding a suitable partitionof the vertices and edges of a hypergraph.

References
1. Gebremedhin, A.H., Manne, F., Pothen, A.: What color is your jacobian? Graph coloring forcomputing derivatives. SIAM Rev. (2005) To appear.
2. Krumke, S., Marathe, M., Ravi, S.: Models and approximation algorithms for channel assignment in radio networks. Wireless Networks 7 (2001) 575 – 584
3. Vazirani, V.V.: Approximation Algorithms. Springer (2001)

806

D. Bozdağ et al.

4. Ferreira, A., Pérennes, S., Richa, A.W., Rivano, H., Stier, N.: Models, complexity and algorithms for the design of multi-fiber wdm networks. Telecommunication Systems 24 (2003)
123 – 138
5. McCormick, S.T.: Optimal approximation of sparse hessians and its equivalence to a graphcoloring problem. Math. Programming 26 (1983) 153 – 171
6. Boman, E.G., Bozdağ, D., Catalyurek, U., Gebremedhin, A.H., Manne, F.: A scalable parallelgraph coloring algorithm for distributed memory computers. (EuroPar 2005, to appear)
7. Gebremedhin, A.H., Manne, F.: Scalable parallel graph coloring algorithms. Concurrency:
Practice and Experience 12 (2000) 1131–1146
8. Gebremedhin, A.H., Manne, F., Woods, T.: Speeding up parallel graph coloring. In: proceedings of Para 2004, Lecture Notes in Computer Science, Springer (2004)
9. Jones, M.T., Plassmann, P.: A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14(1993) 654–669
10. Gebremedhin, A.H., Manne, F., Pothen, A.: Parallel distance- k coloring algorithms fornumerical optimization. In: proceedings of Euro-Par 2002. Volume 2400., Lecture Notes in
Computer Science, Springer (2002) 912–921
11. : (Test data from the parasol project) http://www.parallab.uib.no/projects/parasol/data/.
12. : (University of florida matrix collection) http://www.cise.ufl.edu/research/sparse/matrices/.
13. Strout, M.M., Hovland, P.D.: Metrics and models for reordering transformations. In: proceedings of MSP 2004. (2004) 23–34