A New Implicit Branching Strategy for Exact Maximum Clique

San Segundo Carrillo, Pablo y Tapia Garcia, Cristobal (2010). A New Implicit Branching Strategy for Exact Maximum Clique. En: "22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI", 27/10/2010 - 29/10/2010, Arras, Francia. ISBN 978-1-4244-8817-9.

Descripción

Título: A New Implicit Branching Strategy for Exact Maximum Clique
Autor/es:
  • San Segundo Carrillo, Pablo
  • Tapia Garcia, Cristobal
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI
Fechas del Evento: 27/10/2010 - 29/10/2010
Lugar del Evento: Arras, Francia
Título del Libro: Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI
Fecha: Diciembre 2010
ISBN: 978-1-4244-8817-9
Materias:
Palabras Clave Informales: maximum clique, branch and bound, exact search, coloring
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 (285kB) | Vista Previa

Resumen

We present a new implicit branching strategy for maximum clique. The new strategy is based in Konj and Janečič's improvement over reference MCR algorithm. It uses a fixed initial non increasing degree vertex ordering at every step of the search, to obtain tighter bounds than MCR on average. We show that the new branching strategy integrates nicely with a natural bit model for the domain. This allows for efficient bound computing using bit masking operations, so that overall improvement in performance is achieved. We present empirical validation over structured and random graphs

Más información

ID de Registro: 7907
Identificador DC: http://oa.upm.es/7907/
Identificador OAI: oai:oa.upm.es:7907
URL Oficial: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5670057&tag=1
Depositado por: Memoria Investigacion
Depositado el: 27 Jul 2011 10:28
Ultima Modificación: 20 Abr 2016 16: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