set If multiple colors can be grabbed then the least constraining one is picked If no color in the target set can be grabbed then a color outside the target set is assigned Nodes that are early in the priority sequence are more likely to have a wide range of colors to pick from Nodes that come later may grab colors from earlier nodes  but only if the earlier nodes have other color options within the target set Analyzer. Blame is assigned to ea node whose assigned color is outside the target set with the amount of blame increasing for each additional color that must be added to the target set We ran experiments with several different variations of color based analysis  All of them performed reasonably Prioritizer. The prioritizer modifies the previous sequence of nodes by moving nodes with blame forward in the sequence according to how much blame each received  This is done the same way it is done for the scheduling problems  The initial sequence is a list of nodes sorted in decreasing degree order  with some noise added to slightly shuffle the sort

## 4.2 Experimental Results

We applied swo to a standard set of graph coloring problems  including random graphs and application graphs that model register allocation and class scheduling problems   These were collected for the Second DIMACS Implementation Challenge   Johnson     Trick w hich includes results for several algorithms on these problems  Culberson    Luo Glover Parker Problems range Morgenstern from nodes with     edges to nodes with edges Glover et al is the only paper that is based on a general search technique  TABU
with branch and bound  rather than a graph coloring specific algorithm   This approach with had the worst reported average results in the group  Morgenstern used a distributed IMPASSE algorithm and had the best overall colorings  but also required that the target nmber of colors as well as several other problem specific parameters be passed to the also found good solutions for this problem set sssseen T Their approach used a hybrid of parallel IMPASSE and systematic search on a processor CM
Culberson    Luo used an Iterated Greedy  IG  algorithm that bears some ssimilarity to SWO  IG is the simplest algorithm in the group  Its solution quality falls between the IMPASSE algorithms and TABU but solves the entire set in   to   percent of the time taken by the other methods  Both IG and IMPASSE are discussed further under related work Table   compares swo with the results for IG  Culberson    Luo distributed IMPASSE Morgenstern and TABU
Glover et al For each  one column shows the number of colors required for each problem and the run time in CP seconds Bold face indicates that the number of colors is within     of the best result in the table We used a Pentium Pro     MHz workstation running Linux for the SWO graph coloring experiments The times shown for the other four algorithms are based on those reported in Johnson   Trick The results for IG IMPASSE and TABU are normalized to our times
