Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
An enhanced bitstring encoding for exact maximum clique search in sparse graphs
Año:2017
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
This paper describes BBMCW, a new efficient exact maximum clique algorithm tailored for large sparse graphs which can be bit-encoded directly into memory without a heavy performance penalty. These graphs occur in real-life problems when some form of locality may be exploited to reduce their scale. One such example are correspondence graphs derived from data association problems. The new algorithm is based on the bit-parallel kernel used by the BBMC family of published exact algorithms. BBMCW employs a new bitstring encoding that we denote 'watched', because it is reminiscent of the 'watched literal' technique used in satisfiability and other constraint problems. The new encoding reduces the number of spurious operations computed by the BBMC bit-parallel kernel in large sparse graphs. Moreover, BBMCW also improves on bound computation proposed in the literature for bit-parallel solvers. Experimental results show that the new algorithm performs better than prior algorithms over data sets of both real and synthetic sparse graphs. In the real data sets, the improvement in performance averages more than two orders of magnitude with respect to the state-of-the-art exact solver IncMaxCLQ.
Internacional
Si
JCR del ISI
Si
Título de la revista
Optimization Methods & Software
ISSN
1055-6788
Factor de impacto JCR
0,841
Información de impacto
Datos JCR del año 2015
Volumen
32
DOI
10.1080/10556788.2017.1281924
Número de revista
2
Desde la página
312
Hasta la página
335
Mes
SIN MES
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Jorge Artieda Trigueros (UPM)
  • Autor: Mikhail Batsyn (LATNA)
  • Autor: Panos M. Pardalos (University of Florida)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Centro o Instituto I+D+i: Centro de Automática y Robótica (CAR). Centro Mixto UPM-CSIC
  • Departamento: Ingeniería Eléctrica, Electrónica Automática y Física Aplicada
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)