|
Descripción
|
|
|---|---|
| This paper describes a new very efficient branch-and-bound exact maximum clique algorithm BBMCSP, designed for large and massive sparse graphs which appear frequently in real life problems from different fields. State-of-the-art exact maximum clique algorithms encode the adjacency matrix in full but when dealing with sparse graphs some form of compression is required. The new algorithm is based on a leading bit-parallel non-sparse solver but employs a novel sparse encoding for the adjacency matrix. Moreover, it also improves on recent optimizations proposed in literature for the sparse case such as core-based bounds. Reported results show that it is several orders of magnitude better than state-of-the-art. Moreover, a number of real networks with many millions of nodes are solved in a few seconds. | |
|
Internacional
|
Si |
|
JCR del ISI
|
Si |
|
Título de la revista
|
Computers & Operations Research |
|
ISSN
|
0305-0548 |
|
Factor de impacto JCR
|
1,988 |
|
Información de impacto
|
Q1, Datos JCR del año 2015 |
|
Volumen
|
|
|
DOI
|
10.1016/j.cor.2015.07.013 |
|
Número de revista
|
66 |
|
Desde la página
|
81 |
|
Hasta la página
|
94 |
|
Mes
|
SIN MES |
|
Ranking
|
Area: ENGINEERING, INDUSTRIAL (11/44-Q1) Area: OPERATIONS RESEARCH & MANAGEMENT SCIENCE (19/82-Q1) |