|
Abstract
|
|
|---|---|
| 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. | |
|
International
|
Si |
|
JCR
|
Si |
|
Title
|
Optimization Letters |
|
ISBN
|
1862-4472 |
|
Impact factor JCR
|
1,019 |
|
Impact info
|
Datos JCR del año 2015 |
|
Volume
|
|
|
|
10.1007/s11590-016-1019-3 |
|
Journal number
|
|
|
From page
|
online |
|
To page
|
online |
|
Month
|
MARZO |
|
Ranking
|
Area: MATHEMATICS APPLIED (87/254-Q2) |