2013 | OriginalPaper | Buchkapitel
Solving Clique Covering in Very Large Sparse Random Graphs by a Technique Based on k-Fixed Coloring Tabu Search
verfasst von : David Chalupa
Erschienen in: Evolutionary Computation in Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.