swMATH ID: 11525
Software Authors: San Segundo, Pablo; Tapia, Cristobal
Description: Relaxed approximate coloring in exact maximum clique search. This paper presents selective coloring as a new paradigm for branch-and-bound exact maximum clique search. Approximate coloring has, in recent, years been at the heart of leading solvers in the field. Selective coloring proposes to relax coloring up to a certain threshold. The result is a less informed but lighter decision heuristic.par Different operators for the remaining uncolored vertices give rise to algorithmic variants integrated in a new BBMCL framework. BBMCL allows for an interesting comparison between approximate coloring and degree-based decision heuristics.par The paper also reports extensive empirical tests. Selective coloring algorithms are fastest for a large subset of the graphs considered.
Homepage: http://www.sciencedirect.com/science/article/pii/S0305054813003134
Keywords: combinatorial optimization; approximate coloring; branch-and-bound; global search
Related Software: MaxCliqueDyn; BBMCSP; DIMACS; CPLEX; Algorithm 457; BITSCAN; MINION; SURF; SIFT; k-Vertex-Cut-Problem; Knapsack; SNAP; BBMCW; BHOSLIB; COIN-OR; biicode; LKH
Cited in: 17 Publications

Citations by Year