

![0_image_0.png](0_image_0.png)

parallel IMPASSE are the times it took to find the best solution that was found  not the time it took the algorithm to terminate  which was always   hours   TABU ran until the algorithm determined that it could make no further progress  or an hour had passed  whichever came first The TABU numbers are for a single run on each problem  The numbers for the other to algorithms are averages for runs parallel IMPASSE
runs  distributed IMPASSE  parallel runs  SWO  IG  distributed IMPASSE  on each problem IMPASSE or Figure summarizes the performance of each technique on the set of problems that all of the algorithms solved For each solver the graph indicates the average solution quality and the average amount of time needed to solve the set  The ideal location on the graph is the origin producing high quality solutions in very little time  The points shown for the other techniques are the points reported in each of the papers  The curve shown for swo shows how it performs when given varying amounts of time to solve the set  As the graph sssee to the state of the state of the state of the state of the state of the state of the state of the state of the state.

terms of quality and speed SWO also outperforms IG a graph coloring specific algorithm both in terms of quality and speed The IMPASSE solvers clearly produce the best solutions in the group However IMPASSE is a domain specific method and both solvers represent much more programming effort  The SWO solver uses a general purpose search technique and was implemented in less than a month by a single programmer

## 4.3  Alternate Configurations Of Swo

We note that  as with the scheduling work  our first  naive implementation of SWO for graph coloring produced respectable results Even without color reuse color grabbing or the least constraining heuristic the first free color found was picked SWO matched IG on problems