Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475621 | Computers & Operations Research | 2014 | 8 Pages |
Abstract
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.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.The paper also reports extensive empirical tests. Selective coloring algorithms are fastest for a large subset of the graphs considered.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Pablo San Segundo, Cristobal Tapia,