|
Descripción
|
|
|---|---|
| This paper describes BBMCPara, a new parallel exact maximum clique algorithm tailored for large and massive sparse graphs. The paper first presents a sequential algorithm BBMCSP, which builds on ideas from a leading bit-parallel published algorithm for middle-size graphs. It employs heavy pre-processing and a new sparse bitset encoding to outperform other state-of-the-art algorithms by up to several orders of magnitude over a set of real networks. BBMCPara parallelizes BBMCSP by splitting according to a preprocessing step of the latter. On a 20-core computer, it averages speedups close to an order of magnitude over real graphs of up to 3 million vertices. According to the reported results, BBMCPara appears to be the current fastest algorithm for large and massive real networks to the best of our knowledge. | |
|
Internacional
|
Si |
|
JCR del ISI
|
Si |
|
Título de la revista
|
Optimization Letters |
|
ISSN
|
1862-4472 |
|
Factor de impacto JCR
|
1,019 |
|
Información de impacto
|
Datos JCR del año 2015 |
|
Volumen
|
|
|
DOI
|
10.1007/s11590-016-1019-3 |
|
Número de revista
|
|
|
Desde la página
|
online |
|
Hasta la página
|
online |
|
Mes
|
MARZO |
|
Ranking
|
Area: MATHEMATICS APPLIED (87/254-Q2) |