Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
A parallel maximum clique algorithm for large and massive sparse graphs
Año:2016
Áreas de investigación
  • Ciencias de la computación y tecnología informática,
  • Ingeniería eléctrica, electrónica y automática,
  • Automática
Datos
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)
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Alvaro Lopez
  • Autor: Jorge Artieda Trigueros (UPM)
  • Autor: Panos Pardalos (Universidad de Florida)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • 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 2021 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)