A New Implicit Branching Strategy for Exact Maximum Clique

San Segundo Carrillo, Pablo and Tapia García, Cristóbal (2010). A New Implicit Branching Strategy for Exact Maximum Clique. In: "22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI", 27/10/2010 - 29/10/2010, Arras, Francia. ISBN 978-1-4244-8817-9.

Description

Title: A New Implicit Branching Strategy for Exact Maximum Clique
Author/s:
  • San Segundo Carrillo, Pablo
  • Tapia García, Cristóbal
Item Type: Presentation at Congress or Conference (Article)
Event Title: 22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI
Event Dates: 27/10/2010 - 29/10/2010
Event Location: Arras, Francia
Title of Book: Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI
Date: December 2010
ISBN: 978-1-4244-8817-9
Subjects:
Freetext Keywords: maximum clique, branch and bound, exact search, coloring
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 (285kB) | Preview

Abstract

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

More information

Item ID: 7907
DC Identifier: http://oa.upm.es/7907/
OAI Identifier: oai:oa.upm.es:7907
Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5670057&tag=1
Deposited by: Memoria Investigacion
Deposited on: 27 Jul 2011 10:28
Last Modified: 10 Oct 2018 09:03
  • 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