|
Descripción
|
|
|---|---|
| This paper improves an infra-chromatic bound which is used by the exact branch-andbound maximum clique solver BBMCX (San Segundo et al., 2015) as an upper bound on the clique number for every subproblem. The infra-chromatic bound looks for triplets of colour subsets which cannot contain a 3-clique. As a result, it is tighter than the bound obtained by widely used approximate-colouring algorithms because it can be lower than the chromatic number. The reported results show that our algorithm with the new bound significantly outperforms the state-of-the-art algorithms in a number of structured and uniform random graphs. | |
|
Internacional
|
Si |
|
JCR del ISI
|
Si |
|
Título de la revista
|
Informatica-Lithuan |
|
ISSN
|
0868-4952 |
|
Factor de impacto JCR
|
1,386 |
|
Información de impacto
|
Q1, Datos JCR del año 2015 |
|
Volumen
|
27 |
|
DOI
|
10.15388/Informatica.2016.95 |
|
Número de revista
|
2 |
|
Desde la página
|
463 |
|
Hasta la página
|
487 |
|
Mes
|
ABRIL |
|
Ranking
|
Area: MATHEMATICS APPLIED (47/254-Q1) |