An improved bit parallel exact maximum clique algorithm

San Segundo Carrillo, Pablo and Matía Espada, Fernando and Rodríguez-Losada González, Diego and Hernando Gutiérrez, Miguel (2011). An improved bit parallel exact maximum clique algorithm. "Optimization Letters", v. 4 (n. 3); pp. 3-15. ISSN 1862-4472. https://doi.org/10.1007/s11590-011-0431-y.

Description

Title: An improved bit parallel exact maximum clique algorithm
Author/s:
  • San Segundo Carrillo, Pablo
  • Matía Espada, Fernando
  • Rodríguez-Losada González, Diego
  • Hernando Gutiérrez, Miguel
Item Type: Article
Título de Revista/Publicación: Optimization Letters
Date: 2011
ISSN: 1862-4472
Volume: 4
Subjects:
Freetext Keywords: Maximum clique, Branch and bound, Exact search, Graph
Faculty: E.U.I.T. Industrial (UPM)
Department: Electrónica, Automática e Informática Industrial [hasta 2014]
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (636kB)

Abstract

This paper describes new improvements for BB-MaxClique (San Segundo et al. in Comput Oper Resour 38(2):571–581, 2011 ), a leading maximum clique algorithm which uses bit strings to efficiently compute basic operations during search by bit masking. Improvements include a recently described recoloring strategy in Tomita et al. (Proceedings of the 4th International Workshop on Algorithms and Computation. Lecture Notes in Computer Science, vol 5942. Springer, Berlin, pp 191–203, 2010 ), which is now integrated in the bit string framework, as well as different optimization strategies for fast bit scanning. Reported results over DIMACS and random graphs show that the new variants improve over previous BB-MaxClique for a vast majority of cases. It is also established that recoloring is mainly useful for graphs with high densities.

More information

Item ID: 11804
DC Identifier: http://oa.upm.es/11804/
OAI Identifier: oai:oa.upm.es:11804
DOI: 10.1007/s11590-011-0431-y
Official URL: http://link.springer.com/article/10.1007%2Fs11590-011-0431-y
Deposited by: Memoria Investigacion
Deposited on: 06 Nov 2012 12:03
Last Modified: 22 Sep 2014 10:51
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM