|
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. | |
|
International
|
Si |
|
JCR
|
Si |
|
Title
|
Computers & Operations Research |
|
ISBN
|
0305-0548 |
|
Impact factor JCR
|
1,909 |
|
Impact info
|
|
|
Volume
|
44 |
|
|
10.1016/j.cor.2013.10.018 |
|
Journal number
|
|
|
From page
|
185 |
|
To page
|
192 |
|
Month
|
SIN MES |
|
Ranking
|
Q1 (10 sobre 43 en ENGINEERING, INDUSTRIAL) |