E. Balas et J. Xue, WEIGHTED AND UNWEIGHTED MAXIMUM CLIQUE ALGORITHMS WITH UPPER-BOUNDS FROM FRACTIONAL COLORING, Algorithmica, 15(5), 1996, pp. 397-412
The linear programming relaxation of the minimum vertex coloring probl
em, called the fractional coloring problem, is NP-hard. We describe ef
ficient approximation procedures for both the weighted and unweighted
versions of the problem. These fractional coloring procedures are then
used for generating upper bounds for the (weighted or unweighted) max
imum clique problem in the framework of a branch-and-bound procedure.
Extensive computational testing shows that replacing the standard uppe
r bounding procedures based on various integer coloring heuristics wit
h the somewhat more expensive fractional coloring procedure results in
improvements of the bound by up to one-fourth in the unweighted and u
p to one-fifth in the weighted case, accompanied by a decrease in the
size of the search tree by a factor of almost two.