Watching subgraphs to improve efficiency in maximum clique search

San Segundo Carrillo, Pablo; Tapia Garcia, Cristobal y Lopez, Alvaro (2013). Watching subgraphs to improve efficiency in maximum clique search. En: "The 26th International Conference on Industrial Engineering & Other Application of Applied Intelligent Systems (IEA/AIE)", 17-21/Junio/2013, Amsterdam. ISBN 978-3-319-00650-5.

Descripción

Título: Watching subgraphs to improve efficiency in maximum clique search
Autor/es:
  • San Segundo Carrillo, Pablo
  • Tapia Garcia, Cristobal
  • Lopez, Alvaro
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: The 26th International Conference on Industrial Engineering & Other Application of Applied Intelligent Systems (IEA/AIE)
Fechas del Evento: 17-21/Junio/2013
Lugar del Evento: Amsterdam
Título del Libro: Contemporary Challenges and Solutions in Applied Artificial Intelligence
Fecha: 2013
ISBN: 978-3-319-00650-5
Materias:
Palabras Clave Informales: Branch and bound; Exact search; Bit strings; Efficiency
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 (1MB) | Vista Previa

Resumen

This paper describes a new technique referred to as watched subgraphs which improves the performance of BBMC, a leading state of the art exact maximum clique solver (MCP). It is based on watched literals employed by modern SAT solvers for boolean constraint propagation. In efficient SAT algorithms, a list of clauses is kept for each literal (it is said that the clauses watch the literal) so that only those in the list are checked for constraint propagation when a (watched) literal is assigned during search. BBMC encodes vertex sets as bit strings, a bit block representing a subset of vertices (and the corresponding induced subgraph) the size of the CPU register word. The paper proposes to watch two subgraphs of critical sets during MCP search to efficiently compute a number of basic operations. Reported results validate the approach as the size and density of problem instances rise, while achieving comparable performance in the general case.

Más información

ID de Registro: 33261
Identificador DC: http://oa.upm.es/33261/
Identificador OAI: oai:oa.upm.es:33261
URL Oficial: http://link.springer.com/chapter/10.1007%2F978-3-319-00651-2_16
Depositado por: Memoria Investigacion
Depositado el: 02 Feb 2015 11:58
Ultima Modificación: 05 Feb 2015 09:30
  • 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