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.
Keywords for this software
References in zbMATH (referenced in 3 articles , 1 standard article )
Showing results 1 to 3 of 3.
- Farasat, Alireza; Nikolaev, Alexander G.: Social structure optimization in team formation (2016)
- San Segundo, Pablo; Lopez, Alvaro; Pardalos, Panos M.: A new exact maximum clique algorithm for large and massive sparse graphs (2016)
- San Segundo, Pablo; Tapia, Cristobal: Relaxed approximate coloring in exact maximum clique search (2014)