EfficientColoringofaLargeSpectrumofGraphs

Wehave developedanewalgorithm and software for graph coloringbysystematicallycombiningseveralalgorithmand software development ideas that had crucial impact on the algorithm’sperformance. Thealgorithmexploresthedivideand-conquerparadigm,global search for constrained independent sets using acomputationally inexpensive objective function, assignment of most-constrained vertices to leastconstraining colors, reuse and locality exploration of intermediatesolutions,searchtimemanagement,post-processing lottery-schedulingiterative improvement,andstatistical parameter determination and validation. The algorithm was tested on aset of real-life examples. Wefoundthat hard-tocolor real-life examples are common especially in domains where problem modeling results in denser graphs. Systematic experimentations demonstrated that for numerous instances the algorithm outperformed all other implementationsreportedinliteratureinsolutionqualityandrun-time.