2013 | OriginalPaper | Chapter
Solving Clique Covering in Very Large Sparse Random Graphs by a Technique Based on k-Fixed Coloring Tabu Search
Author : David Chalupa
Published in: Evolutionary Computation in Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We propose a technique for solving the
k
-fixed variant of the clique covering problem (
k
-CCP), where the aim is to determine, whether a graph can be divided into at most
k
non-overlapping cliques. The approach is based on labeling of the vertices with
k
available labels and minimizing the number of non-adjacent pairs of vertices with the same label. This is an inverse strategy to
k
-fixed graph coloring, similar to a tabu search algorithm TabuCol. Thus, we call our method TabuCol-CCP. The technique allowed us to improve the best known results of specialized heuristics for CCP on very large sparse random graphs. Experiments also show a promise in scalability, since a large dense graph does not have to be stored. In addition, we show that Γ function, which is used to evaluate a solution from the neighborhood in graph coloring in
$\mathcal{O}(1)$
time, can be used without modification to do the same in
k
-CCP. For sparse graphs, direct use of Γ allows a significant decrease in space complexity of TabuCol-CCP to
$\mathcal{O}(|E|)$
, with recalculation of fitness possible with small overhead in
$\mathcal{O}(\log \deg(v))$
time, where deg(
v
) is the degree of the vertex, which is relabeled.