An improved bit parallel exact maximum clique algorithm

San Segundo Carrillo, Pablo; Matía Espada, Fernando; Rodríguez-Losada González, Diego y 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.

Descripción

Título: An improved bit parallel exact maximum clique algorithm
Autor/es:
  • San Segundo Carrillo, Pablo
  • Matía Espada, Fernando
  • Rodríguez-Losada González, Diego
  • Hernando Gutiérrez, Miguel
Tipo de Documento: Artículo
Título de Revista/Publicación: Optimization Letters
Fecha: 2011
Volumen: 4
Materias:
Palabras Clave Informales: Maximum clique, Branch and bound, Exact search, Graph
Escuela: E.U.I.T. Industrial (UPM) [antigua denominación]
Departamento: Electrónica, Automática e Informática Industrial [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (636kB)

Resumen

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.

Más información

ID de Registro: 11804
Identificador DC: http://oa.upm.es/11804/
Identificador OAI: oai:oa.upm.es:11804
Identificador DOI: 10.1007/s11590-011-0431-y
URL Oficial: http://link.springer.com/article/10.1007%2Fs11590-011-0431-y
Depositado por: Memoria Investigacion
Depositado el: 06 Nov 2012 12:03
Ultima Modificación: 22 Sep 2014 10:51
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM