A Scalable Parallel Graph Coloring Algorithm forDistributed Memory Computers
Erik G. Boman1 , Doruk Bozdağ2 , Umit Catalyurek2? , Assefaw H. Gebremedhin3?? ,and Fredrik Manne4
12Sandia National Laboratories, USA, egboman@sandia.gov? ? ? ,Ohio State University, USA, bozdagd@ece.osu.edu and umit@bmi.osu.edu
3
Old Dominion University, USA, assefaw@cs.odu.edu
4
University of Bergen, Norway, Fredrik.Manne@ii.uib.no

Abstract. In large-scale parallel applications a graph coloring is often carriedout to schedule computational tasks. In this paper, we describe a new distributedmemory algorithm for doing the coloring itself in parallel. The algorithm operates
in an iterative fashion; in each round vertices are speculatively colored based onlimited information, and then a set of incorrectly colored vertices, to be recoloredin the next round, is identified. Parallel speedup is achieved in part by reducing
the frequency of communication among processors. Experimental results on a PC
cluster using up to 16 processors show that the algorithm is scalable.

1 Introduction
In many parallel scientific computing applications computational dependencies are modeled using a graph, and a coloring of the vertices of the graph is used as a subroutine
to identify independent tasks that can be performed concurrently. See [8] and the references therein for examples. In such cases, the computational graph is often distributed
among the processors, and hence the coloring itself needs to be performed in parallel.
For these applications, fast greedy coloring algorithms that work well in practice areoften preferred over slower local improvement heuristics that might use fewer colors.
This paper deals with the parallelization of such fast greedy coloring algorithms
and presents an efficient parallel coloring algorithmic scheme designed for distributed
memory parallel computers. Several variations of the basic scheme are discussed. Ouralgorithms are implemented using MPI and experiments conducted on a 16-node PC
cluster using several large graphs indicate that our approach is scalable.
The basic idea in the algorithm is to partition the graph among the available processors and let each processor be responsible for the coloring of the vertices assigned to it.
Every processor colors its local vertices in steps of s vertices at a time in a sequential
fashion. Between each step the processors exchange recent color information. Sincea processor colors its local vertices with incomplete color information, conflicts may
arise, and these are detected in a separate phase. The algorithm proceeds iteratively by?

This research was supported in part by Sandia National Laboratories under Doc.No: 283793,
Ohio Supercomputing Center #PAS0052.
??
Supported by the U.S. National Science Foundation grant ACI 0203722.
???
Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin company, for the U.S. Department of Energy’s National Nuclear Security Administration undercontract DE-AC04-94AL85000.

2
recoloring vertices involved in conflicts. With an appropriate choice of a value for s,
the number of ensuing conflicts can be kept low while at the same time preventing theruntime from being dominated by the sending of a large number of small messages.

2 Previous WorkA coloring of a graph is an assignment of positive integers (called colors) to its vertices
such that no two adjacent vertices receive the same color. Finding a coloring of a generalgraph that minimizes the number of colors used is an NP-hard problem [6]. Moreover,the problem is difficult to approximate [4]. In practice, however, greedy sequential coloring heuristics have been found to be quite effective [3]. These greedy heuristics are
inherently sequential and hence difficult to parallelize.
A number of previously suggested parallel graph coloring algorithms rely on various ways of computing an independent set in parallel. A characteristic feature of independent set based parallel coloring algorithms is that a vertex is assigned a colorthat is never changed at a later point in the algorithm. In such algorithms, while coloring a vertex v, the colors of already colored neighbors of v must be known, and noneof the uncolored neighbors of v can be colored at the same time as v. The works ofJones and Plassmann [11], Gjertsen et al. [9], and Allwright et al. [1] are examples ofsuch approaches. All of these algorithms are designed for distributed memory parallel
computers and rely on partitioning a graph into the same number of components as
there are processors. Each component, including information about its inter- and intracomponent edges, is assigned to and colored by one processor.
To overcome the restriction that two adjacent vertices on different processors cannot be colored at the same time, Johansson [10] proposed a distributed algorithm where
each processor is assigned exactly one vertex. The vertices are then colored simultaneously by randomly choosing a color from the interval [1, ∆ + 1], where ∆ is the
maximum vertex degree in the graph. This may lead to an inconsistent coloring, andhence the process needs to be repeated recursively for the vertices that did not receive
permissible colors. Finocchi et al. [5] performed extensive sequential simulations of avariant of Johansson’s algorithm where the upper-bound on the range of permissible
colors is initially set to be smaller than ∆ + 1 and then increases only when needed.
Gebremedhin and Manne [8] developed a parallel graph coloring algorithm suitable
for shared memory computers. In this algorithm, each processor is assigned equally
many vertices to color. A processor colors its vertices in a sequential fashion, at eachstep assigning a vertex the smallest color not used by any of its neighbors (both onor off-processor). An inconsistent coloring arises only when a pair of adjacent vertices
that reside on different processors is colored simultaneously. Inconsistencies are thendetected in a subsequent phase and resolved in a final sequential phase.

3 A New Algorithm
Here we describe a new distributed-memory parallel graph coloring algorithm. In thespirit of the BSP model [2], the algorithm is organized as a sequence of supersteps.
A superstep has distinct, rather than intermingled, computation and communication
phases.

3
A partitioning of the graph among the processors classifies the vertices into interior
and boundary vertices. An interior vertex is a vertex all of whose neighbors are locatedon the same processor as itself. A boundary vertex has at least one neighbor located on adifferent processor. Clearly, the subgraphs induced by interior vertices are independentof each other and hence can be colored concurrently trivially. Coloring the remainderof the graph in parallel requires communication and coordination among the processors
and this is the main issue in the algorithm being described.
3.1 The Basic Scheme
At the highest level, our algorithm is iterative—it operates in rounds. In each roundthere are two phases, a tentative coloring and a conflict detection phase. The former isorganized into supersteps while the latter is not, since no communication is required.
In every superstep each processor colors s vertices in a sequential manner, where s isan input parameter to the algorithm, using color information available at the beginningof the superstep, and then exchanges recent color information with other processors.
In particular, in the communication phase of a superstep, a processor sends the colorsof its boundary vertices to other processors and receives relevant color informationfrom other processors. In this scenario, if two adjacent vertices located on two different
processors are colored during the same superstep, they may receive the same color andhence cause a conflict. The purpose of the second phase of a round is to detect suchconflicts and accumulate a list of vertices on each processor to be recolored in the next
round. Since it is not necessary to recolor both endpoints of a conflict edge only oneof the involved processors will add a vertex to its list. The processor that will do therecoloring is determined in a random fashion in order to achieve an even distribution of
the vertices to be colored in the next round.
The conflict detection phase does not require communication since every processor
has acquired a complete knowledge of the colors of the neighbors of its vertices at theend of the tentative coloring phase. The algorithm terminates when there is no more
processor with a nonempty list of vertices to be recolored. Algorithm 1 outlines thisscheme in more detail.
The rationale for dividing the coloring phase of a round in supersteps, rather thancommunicating after a single vertex is colored, is to reduce communication frequency
and thereby reduce communication time. However the number of supersteps used (equivalently, the number of vertices colored in a superstep) is also closely related to the likelihood of conflicts and consequently the number of rounds. The lower the number ofsupersteps (the higher the number of vertices colored per superstep) the higher the likelihood of conflicts and hence the higher the number of rounds required. Choosing avalue for s that minimizes the overall runtime is therefore a compromise between thesetwo contradicting requirements. An optimal value of s would depend on such factors
as the size and density of the input graph, the number of processors available, and themachine architecture and network.
Note that the formulation of Algorithm 1 is general enough to encompass the algorithms of Johannsson [10], Finocchi et al. [5], and Gebremedhin and Manne [8]. Setting
p = n (and s = 1) and choosing the color of a vertex in Line 10 appropriately, gives
the algorithms of Johannsson and Finocchi et al. Setting s = 1, restricting Algorithm 1

4
Algorithm 1 An iterative parallel graph coloring algorithm
1: procedure PARALLEL C OLORING(G = (V, E), s)
2:
Initial data distribution: V is partitioned into p subsets V1 , . . . , Vp ; processor Pi
owns Vi , stores edges Ei incident on Vi , and stores the identity of processors
hosting the other endpoints of Ei .
3:
on each processor Pi , i ∈ P = {1, . . . , p}4:
Ui ← Vi. Ui is the current set of vertices to be colored5:
while ∃j ∈ P, Uj 6= ∅ do
6:
if Ui 6= ∅ then7:
Partition Ui into `i subsets Ui,1 , Ui,2 , . . . , Ui,`i , each of size s
8:for k ← 1 to `i do. each k corresponds to a superstep
9:for each v ∈ Ui,k do
10:
assign v a permissible color
11:
Send colors of boundary vertices in Ui,k to relevant processors
12:
Receive color information from other processors
13:
Wait until all incoming messages are successfully received
14:
Ri ← ∅. Ri is a set of vertices to be recolored15:
for each boundary vertex v ∈ Ui do
16:
if ∃(v, w) ∈ E s.t. color(v) = color(w) and r(v) ≤ r(w) then17:
Ri ← Ri ∪ {v}. r(v) is a random number
18:
Ui ← R i
19:

to one round, and resolving conflicts sequentially gives the algorithm of Gebremedhinand Manne.
3.2 Variations
For the sake of generality, Algorithm 1 leaves several issues unspecified. In the sequel,
we discuss such issues, in each case pointing out available alternatives.
(i) Initial partitioning. In a parallel application, the graph is usually already distributed
among the processors in a reasonable way. However, if this is not the case, a “good” data
distribution needs to be computed. The number of conflicts in the algorithm depends on
several factors including the number of boundary vertices and the number of edges
between these. Thus using a graph partitioner such as Metis [12] should help reduce thenumber of conflicts as well as the amount of communication.
(ii) Distinguishing between interior and boundary vertices. As mentioned earlier, thesubgraphs induced by interior vertices are independent of each other and can therefore
be colored concurrently without any communication. Hence, in the context of Algorithm 1, the interior vertices can be colored before, after, or interleaved with boundary
vertices. Algorithm 1 is presented assuming the last option. Coloring the interior vertices first may produce fewer conflicts when using a regular First-Fit coloring scheme,
since the subsequent coloring of boundary vertices is performed with a larger spectrumof available colors. Coloring boundary vertices first may be advantageous with color
selection variants such as Staggered First-Fit (see the discussion later in this section).

5(iii) Synchronous vs. asynchronous supersteps. In Algorithm 1, the supersteps can bemade to run in a synchronous fashion by introducing explicit synchronization barriers
at the end of each superstep. An advantage of this mode is that in the conflict detection
phase, the color of a boundary vertex needs to be checked only against its neighbors
colored at the same superstep. The obvious disadvantage is that the barriers, in addition
to the associated overhead, cause some processors to be idle while others complete theirsupersteps. Alternatively, the supersteps can be made to run asynchronously, without
explicit barriers at the end of each superstep. Each processor would then only process
and use the color information that has been completely received when it is checking
for incoming messages. Any color information that has not reached a processor at thisstage would thus be delayed from being used until a later superstep. Due to this, in theconflict detection phase, the color of a boundary vertex needs to be checked against allof its off-processor neighbors. Also, it is possible that the asynchronous version resultsin more conflicts than the synchronous one since a superstep on one processor now canoverlap with more than one superstep on another processor.
(iv) Choice of color. The choice of a permissible color in Line 10 of Algorithm 1 can bemade in different ways. The strategy employed affects (1) the number of colors used by
the algorithm, and (2) the likelihood of conflicts, and thus the number of rounds requiredby the algorithm. Both of these quantities are desired to be as small as possible, anda coloring strategy typically reduces one of the quantities at the expense of the other.
Here, we present two strategies: First-Fit (FF) and Staggered First-Fit (SFF). In FF eachprocessor chooses the smallest permissible color from the interval [1, C], where C is thecurrent largest color used. If no such color exists, the new color C + 1 is chosen. SFF
uses an initial estimate K of the number of colors needed for the input graph. Processor
Pi chooses the smallest permissible color from the interval [d iK
p e, K]. If no such color
iK
exists, then the smallest permissible color in [1, b p c] is chosen. If there is still no suchcolor, the smallest permissible color greater than K is chosen. Unlike FF, the search fora color in SFF starts from different “base colors” for each processor. Hence the latter islikely to result in fewer conflicts than the former. Other color selection strategies thathave been suggested include the randomized techniques of Gebremedhin et al. [7] andFinocchi et al. [5].

4 Experiments
In this section, we present results from experiments carried out on a 16-node PC cluster
equipped with dual 900 MHz Intel Itanium 2 CPUs and 4 GB memory. The nodes of
the cluster are interconnected via switched Myrinet 2000 network. Our test set consistsof 19 graphs obtained from molecular dynamics and finite element applications [8, 13].
Table 1 displays the structural properties of the test graphs, including maximum, minimum, and average degree. The table also displays the number of colors and the runtime
in seconds used by a sequential FF algorithm when run on a single node of our test platform. All of the results presented in this section are average performance results over
all of the graphs presented in Table 1. Each individual test is an average of 5 runs. In thetiming of the parallel coloring code, we assume the graph to be initially partitioned anddistributed among the nodes of the parallel machine. Hence, the times reported concern
only coloring.

6
name

|V |

|E|

DegreeSeq. First-Fit
max min avg #colors time
HIV-2
11,414
15,270 8 1 2.68
5 0.007HIV-4
11,414130,332 39 6 22.84
17 0.034
HIV-6
11,414
412,623 116 13 72.30
45 0.099
HIV-1011,414 1,655,383 454 35 290.06
176 0.387
popc-br-2 24,916
31,449 7 1 2.52
5 0.032
popc-br-4 24,916
255,047 43 2 20.47
21 0.067
popc-br-6 24,916
850,043 125 2 68.23
49 0.206
popc-br-10 24,916 3,587,724 514 2 287.98
173 0.84
er-gre-2
36,57353,046 8 0 2.90
5 0.022er-gre-4
36,573451,355 42 3 24.68
19 0.116
er-gre-6
36,573 1,482,904 116 11 81.09
47 0.357
er-gre-10 36,573 6,511,122 460 79 356.06
174 1.515
apoa1-2
92,224
139,351 8 1 3.02
5 0.057
apoa1-4
92,224 1,131,436 43 2 24.54
20 0.293
apoa1-6
92,224 3,864,429 123 13 83.81
49 0.928
apoa1-10 92,224 17,100,850 503 54 370.85
182 3.993
598a
110,971 741,934 26 5 13.37
12 0.310
144
144,649 1,074,393 26 4 14.86
11 0.219
auto
448,695 3,314,611 37 4 14.77
13 0.984
Table 1. Properties of the test graphs.

In our experiments, we considered two ways of partitioning the vertices of a graph.
In the first case, the vertex set, with the vertices in their natural order, is partitioned into
p contiguous blocks of (almost) equal size. Such a block partitioning does not attempt
to minimize cross-edges, though the structure of the natural order is exploited. In thesecond case, the vertex set is partitioned into p disjoint subsets of nearly equal size
such that the number of cross-edges is small. For this we used the graph partitioning
software Metis [12], with an option known as VMetis that also attempts to minimize
the communication volume.
The first set of experiments, shown in Figures 1 and 2, are conducted to assess
the effects of the following three issues: block partitioning using the natural order (N)vs. partitioning using VMetis (V); coloring interior vertices first (I), boundary vertices
first (B), or interleaved (U); and using synchronous (S) vs. asynchronous supersteps(A). In all of these experiments we use FF for selecting the color of a vertex. A 3-letter
acronym reflecting the options discussed above is used in Figures 1 and 2.
Figure 1 displays the number of conflicts (normalized with respect to the total number of vertices) for the parallel coloring algorithm for different combinations of these
options while varying the superstep size and the number of processors. In Figure 1(a),we show results for the case where the number of processors is 8. Similar trends wereobserved for other number of processors. When varying the number of processors, the7superstep size is set to 100. In the interleaved mode the superstep size gives the numberof boundary vertices colored in each superstep.

0.08

0.1

VBA
VUA
VIA
NIS
VIS

0.07

Number of conflicts / |v|

Number of conflicts / |v|

0.12

0.08

0.06

0.04

0.02

0

0.06

VBA
VUA
VIA
NIS
VIS

0.05
0.04
0.03
0.02
0.01

100

200

300

400

500

Superstep size

(a)

600

700

800

0
2

4

6

8

10

12

14

16

Number of processors(b)Fig. 1. Number of conflicts while varying (a) superstep size s for p = 8, and (b) numberof processors for s = 100.
Figure 1(a) and 1(b) shows that for all configurations the number of conflicts increases as the superstep size and the number of processors, respectively, increases. The
two figures also show that asynchronous supersteps result in more conflicts than synchronous supersteps, and that graph partitioning using Metis results in fewer conflicts
than block partitioning. In the case where block partitioning is used, only the combination of options (NIS) that gave the fewest conflicts is shown. When using Metis withsynchronous supersteps we also only show the configuration (VIS) that gave the least
number of conflicts. Using the boundary first and unordered options gave only slightly
worse results than the presented ones. In terms of the number of conflicts, the results in
Figures 1(a) and 1(b) suggest that the best result is obtained by partitioning the graphusing Metis and using a small superstep size while running supersteps synchronously.
As can be observed from the figure in the asynchronous case, the order in which
the boundary and interior vertices are colored has no major impact on the number ofconflicts.
In all of our experiments, the number of rounds the algorithm has to iterate wasobserved to be consistently low, varying between two and five, for every configuration
we tried. This is a consequence of the fact that the number of initial conflicts is small andthen drops rapidly between successive rounds. As long as Metis is used the total numberof conflicts is within 10% of the total number of vertices in all of the configurations
considered. Thus more than 90% of the sequential work is performed in the first round.
This indicates that the increase in the number of vertices that need to be colored whengoing from a sequential to a parallel algorithm is fairly low for the test set we use. We
also note that the number of colors used stays fairly low in all of our experiments andon the average, it does not increase by more than 4% of that used by the (sequential) FF
coloring scheme.
Figure 2(a) displays speedup values for the several variations of the parallel coloringalgorithm while varying the superstep size s for a fixed number of processors p = 8.
We show the NIA configuration (as opposed to NIS in Figure 1) as it gave the best

8
9

6

8

5

7

4.5

6

SpeedupSpeedup

5.5

4
3.5
3

2

100

200

300

400

500

Superstep size

(a)

600

700

5
4
3

VIA
VUA
VBA
VIS
NIA

2.5

VIA
VUA
VBA
VIS
NIA

2

800

1
2

4

6

8

10

12

14

16

Number of processors(b)Fig. 2. Speedup while varying (a) superstep size s for p = 8, and (b) number of processors for s = 100.
speedup when not using Metis to partition the graph. As can be seen from the figure,the optimum value for s is close to 100 for all variants. Thus using s = 100 seems to be agood compromise between balancing the conflicting issues of increased message startup
costs versus the number of conflicts. However, the manner in which the algorithm isconfigured seems to be more important than the superstep size. It is always better to use
asynchronous communication than synchronous. Also, as can be seen from the figurecoloring interior vertices first is slightly better than coloring the vertices interleaved
which again is better than coloring the boundary vertices first.
In Figure 2(b) the speedup obtained as the number of processors is varied while
using a superstep size of 100 is shown. The trends observed in Figure 2(b) are similar to those in Figure 2(a). The best average speedup, over all test cases, was about
8.5 while using 16 processors. However, for particular test cases, we have observed a
speedup value as high as 12.5 while using 16 processors. The worst result observed wasa speedup of 3.2 on 16 processors. “Medium” dense graphs tend to give better speedup
values than very sparse or very dense graphs.
Our next set of experiments concerns the different coloring schemes as discussed in
Section 3. The results are shown in Figure 3(a) (conflicts), and Figure 3(b) (speedup).
In the figures the labels I and B show whether the interior vertices or the boundary
vertices are colored first, while the second letter correspond to the FF (F) and the SFF(S) color selection scheme. In all of these experiments Metis is used for partitioning andthe communication is done asynchronously. For SFF we use the number of colors foundby sequential FF as our initial estimate of the number of colors. Coloring the vertices
in an interleaved fashion gave similar results as those in the figures and are not shown
here.
As expected, the SFF scheme gives fewer conflicts than the FF scheme. But as canbe seen from Figure 3(b) in terms of speedup this is offset by the higher overhead
associated with determining the correct color in the SFF scheme. Also, the SFF scheme
has the disadvantage of requiring an a priori estimate on the expected number of colors.
The speedup achieved by our approach stems from two sources: partitioning and the“core” algorithm. Partitioning using Metis makes a trivial parallelization of the coloringof interior vertices possible. The “core” algorithm is a nontrivial way of coloring the

9
9

0.08

8

0.06

7

0.05

6

Speedup

Number of conflicts / |v|

0.07

IF
BF
IS
BS

0.04
0.03

5
4

0.02

3

0.01

2

0
2

4

6

8

10

12

14

1
2

16

IS
IF
BS
BF

4

6

8

10

12

14

16

Number of processors

Number of processors

(a)

(b)

Fig. 3. Effect of the color selection algorithm on (a) the number of conflicts, and (b)speedup while using a superstep length of s = 100.
boundary vertices in parallel. Figure 4(a) shows the percentage of boundary vertices forthe graphs in Table 1 when using block partitioning with the natural vertex ordering(blue), and when using Metis (red). As one can see the number of boundary vertices
increases with the number of processors being used. Thus it is difficult to measure theparticular speedup from coloring just the boundary vertices since the amount of work
performed changes with the number of processors. In order to give some indication of
the performance of the algorithm on the boundary vertices we present Figure 4(b). Thisshows the speedup when coloring three random graphs each containing 32000 vertices
and with average vertex degrees 3, 20, and 70 respectively. For these experiments weused the NIA configuration with the vertices colored according to the SFF scheme.
Since the vertices are ordered according to their natural order almost all the vertices
become boundary vertices (see the black curve in Figure 4(a)). Thus this can be viewed
as applying more processors while keeping the number of boundary vertices fixed. Since
we are in effect traversing the graph at least twice (for coloring and verification) wecannot expect to get a speedup of more than p/2. Based on this the observed maximum
speedup of more than 6 when using 16 processors is quite good.

100

6
80

d=70
d=20
d=3

5

70

Speedup% Boundary vertices

90

60
50
40

4

3

30

2
20
N on Random
N on Table 1
V on Table 1

10
0
2

4

6

8

10

12

Number of processors

(a)

14

1
16

2

4

6

8

10

12

14

16

Number of processors(b)Fig. 4. (a) Percentage of boundary vertices for graphs in Table 1 (blue and red), andrandom graphs (black). (b) Speedup for random graphs of various average degrees.

10

5 Conclusion
We have developed an efficient and truly scalable parallel graph coloring algorithm
suitable for a distributed memory computer. The algorithm is flexible and can easily
be tuned to suit the nature of the graph to be colored and the specifics of the hardware
being used. The scalability of the algorithm has been experimentally demonstrated. Thisshould be seen in light of the fact that previous distributed-memory parallel coloringalgorithms, such as the algorithm of Jones and Plassmann [11], did not give any speedup
when coloring the boundary vertices as more processors are applied.
Even though our main objective has been to achieve parallel speedup, being able toperform coloring in a distributed setting where the graph is already partitioned among
the processors is an important functionality in itself.
In the future we plan to experiment with more sophisticated color selection schemesthat may further reduce the number of conflicts. We are also considering how to generalize the algorithm to other coloring problems such as distance-2 graph coloring andhypergraph coloring, both of which have important applications in scientific computing.

References
1. J.R. Allwright, R. Bordawekar, P. D. Coddington, K. Dincer, and C.L. Martin. A comparisonof parallel graph coloring algorithms. Technical Report NPAC technical report SCCS-666,
Northeast Parallel Architectures Center at Syracuse University, 1994.
2. R. H. Bisseling. Parallel Scientific Computation: A Structured Approach Using BSP and
MPI. Oxford, 2004.
3. T. F. Coleman and J. J More. Estimation of sparse jacobian matrices and graph coloring
problems. SIAM J. Numer. Anal., 1(20):187–209, 1983.
4. P. Crescenzi and V. Kann.
A compendium of NP optimization problems.
http://www.nada.kth.se/˜viggo/wwwcompendium/.
5. I. Finocchi, A. Panconesi, and R. Silvestri. Experimental analysis of simple, distributed
vertex coloring algorithms. In proc. of SODA 02, 2002.
6. M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman, 1979.
7. A. H. Gebremedhin, F. Manne, and A. Pothen. Parallel distance-k coloring algorithms fornumerical optimization. In proc. of Euro-Par 2002, LNCS, Springer, 2400:912–921, 2002.
8. A. H. Gebremedhin and F. Manne. Scalable parallel graph coloring algorithms. Concurrency: Practice and Experience, 12:1131–1146, 2000.
9. R. K. Gjertsen Jr., M. T. Jones, and P. Plassmann. Parallel heuristics for improved, balanced
graph colorings. J. Par. and Dist. Comput., 37:171–186, 1996.
10. Ö. Johansson. Simple distributed δ + 1-coloring of graphs. Inf. Proc. Letters, 70:229–232,
1999.
11. M. T. Jones and P. Plassmann. A parallel graph coloring heuristic. SIAM J. Sci. Comput.,
14(3):654–669, 1993.
12. G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregulargraphs. SIAM J. Sci. Comput., 20(1), 1999.
13. M. Mills Strout and P. D. Hovland. Metrics and models for reordering transformations. In
proc. of MSP 2004, pages 23–34, 2004.