## Online compendium to the article: |

In Ed. P. Festa, Proceedings of the 9th International Symposium on Experimental Algorithms 2010,

Lecture Notes in Computer Science, Springer

- All instances listed below: 520 instances of 500 vertices (.tgz, 64MB), 740 instances of 1000 vertices (.tgz, 344MB)
- A C++ source code implementing construction heuristics (ROS, DSATUR, RLF) and local search methods, among them TabuCol (De Werra, 1990) and Hybrid Evolutionary Algorithm (Galiner and Hao, 1999) gcp-v3_73.tgz. (updated on November 11, 2010 GCP-v5.00.tgz).
- A C program to verify solutions gcp_check_sol.
- Results for machine benchmarking using the programs available at the past DIMACS challanges.

Tot. Size Type Density Variability Hidden colouring graphs 500 G 0.1 0 5 10 10 | | | 1 5 10 10 | | | no – 10 | | 0.5 0 20 30 40 50 60 25 | | | 1 20 30 40 50 60 25 | | | no – 10 | | 0.9 0 20 30 40 60 80 100 120 140 40 | | | 1 20 30 40 60 80 100 120 140 40 | | | no – 10 | U 0.1 0 10 20 10 | | | 1 10 20 10 | | | no – 10 | | 0.5 0 20 30 40 50 60 70 80 90 100 110 50 | | | 1 20 30 40 50 60 70 80 90 100 110 50 | | | no – 10 | | 0.9 0 100 150 200 250 300 25 | | | 1 100 150 200 250 300 25 | | | no – 10 | W 0.1 0 5 10 10 | | | 1 5 10 10 | | | no – 10 | | 0.5 0 20 30 40 50 60 25 | | | 1 20 30 40 50 60 25 | | | no – 10 | | 0.9 0 30 60 90 120 20 | | | 1 30 60 90 120 20 | | | no – 10 1000 G 0.1 0 5 10 20 15 | | | 1 5 10 20 15 | | | no – 10 | | 0.5 0 20 30 40 50 60 70 80 90 100 110 120 130 140 75 | | | 1 20 30 40 50 60 70 80 90 100 110 120 130 140 75 | | | no – 10 | | 0.9 0 20 50 100 150 200 250 30 | | | 1 20 50 100 150 200 250 30 | | | no – 10 | U 0.1 0 20 30 40 50 20 | | | 1 20 30 40 50 20 | | | no – 10 | | 0.5 0 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 95 | | | 1 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 95 | | | no – 10 | | 0.9 0 100 200 300 400 500 600 30 | | | 1 100 200 300 400 500 600 30 | | | no – 10 | W 0.1 0 10 20 10 | | | 1 10 20 10 | | | no – 10 | | 0.5 0 20 30 40 50 60 70 80 90 40 | | | 1 20 30 40 50 60 70 80 90 40 | | | no – 10 | | 0.9 0 30 90 150 220 20 | | | 1 30 90 150 220 20 | | | no – 10

The computation time that *TS*_{N1} needs to perform *I _{max}* iterations
varies due to several factors.

In Figure 1 left, we plot the probability of
finding a feasible colouring and an improvement in solution quality
(i.e., a decrease in the number of colour conflicts) after a certain
number of iterations. The graph is obtained by recording the last
corresponding events occurred in a run of *TS*_{N1} on each of the 740
random graphs of size 1000. *TS*_{N1} was run on all graphs for a maximum
number of 100 × *I _{max}* iterations. The curves correspond to the
empirical survival distributions of the event “finding a colouring with
less constraint violations” or “finding a feasible colouring”. In
other words, each point indicates the probability of finding a graph
where improvements in the number of constraint violations or in the
number of colours can still occur after a certain number of iterations,
reported on the

Both types of improvements after 50 × *I _{max}* iterations occurred
only in 10 graphs, that is, with a probability lower than 0.02. The
number of colouring violations in these extreme cases was below 13 and,
we should not discard the possibility that further improvements could
have been possible with longer runs. Therefore, these data should be
treated as censored data and the curve be truncated. Nevertheless, for
730 of the 740 graphs no further improvement in the solution occurred in
the last 50 ×

In the light of these results, 10 × *I _{max}* would have been a
better choice for the termination criterion of

In Figure 1, right, we investigate the computation
time corresponding to *I _{max}* iterations on graphs of 1000 vertices.
Clearly, the reason for uncommonly long run times for

The use of SLS heuristics gives a
significant improvement over the initial solution of *RLF*. In Figure
2, we show the distribution of differences between the
best solutions found in a graph by the SLS heuristics and the initial
*RLF* solution. We distinguish two main patterns which have an impact on
the entity of the improvement. First, the improvement increases
considerably with size and edge density for Uniform and Weight Biased
graphs and it can reach 105 colours of improvement in the case of Weight
Biased graphs. Second, in Geometric graphs, the improvement is smaller
than for the other two types of graphs and more pronounced in graphs of
density 0.5. These results on the Geometric graphs together with the
results of *Ex*-*DSATUR* on those graphs let us conclude that on these
graphs *RLF* finds already a near-optimal solution.