Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
A new exact maximum clique algorithm for large or massive sparse graphs
Año:2016
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
This paper describes a new very efficient branch-and-bound exact maximum clique algorithm BBMCSP, designed for large and massive sparse graphs which appear frequently in real life problems from different fields. State-of-the-art exact maximum clique algorithms encode the adjacency matrix in full but when dealing with sparse graphs some form of compression is required. The new algorithm is based on a leading bit-parallel non-sparse solver but employs a novel sparse encoding for the adjacency matrix. Moreover, it also improves on recent optimizations proposed in literature for the sparse case such as core-based bounds. Reported results show that it is several orders of magnitude better than state-of-the-art. Moreover, a number of real networks with many millions of nodes are solved in a few seconds.
Internacional
Si
JCR del ISI
Si
Título de la revista
Computers & Operations Research
ISSN
0305-0548
Factor de impacto JCR
1,988
Información de impacto
Q1, Datos JCR del año 2015
Volumen
DOI
10.1016/j.cor.2015.07.013
Número de revista
66
Desde la página
81
Hasta la página
94
Mes
SIN MES
Ranking
Area: ENGINEERING, INDUSTRIAL (11/44-Q1) Area: OPERATIONS RESEARCH & MANAGEMENT SCIENCE (19/82-Q1)
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Pablo San Segundo Carrillo (UPM)
  • Autor: Alvaro Lopez Antequera
  • 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)