Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
A parallel maximum clique algorithm for large and massive sparse graphs
Year:2016
Research Areas
  • Information technology and adata processing,
  • Electric engineers, electronic and automatic (eil),
  • Automatic
Information
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)
Participants
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Alvaro Lopez
  • Autor: Jorge Artieda Trigueros (UPM)
  • Autor: Panos Pardalos (Universidad de Florida)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Control Inteligente
  • Centro o Instituto I+D+i: Centro de Automática y Robótica (CAR). Centro Mixto UPM-CSIC
S2i 2019 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)