Watching subgraphs to improve efficiency in maximum clique search

San Segundo Carrillo, Pablo and Tapia García, Cristóbal and Lopez, Alvaro (2013). Watching subgraphs to improve efficiency in maximum clique search. In: "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.

Description

Title: Watching subgraphs to improve efficiency in maximum clique search
Author/s:
  • San Segundo Carrillo, Pablo
  • Tapia García, Cristóbal
  • Lopez, Alvaro
Item Type: Presentation at Congress or Conference (Article)
Event Title: The 26th International Conference on Industrial Engineering & Other Application of Applied Intelligent Systems (IEA/AIE)
Event Dates: 17-21/Junio/2013
Event Location: Amsterdam
Title of Book: Contemporary Challenges and Solutions in Applied Artificial Intelligence
Date: 2013
ISBN: 978-3-319-00650-5
Subjects:
Freetext Keywords: Branch and bound; Exact search; Bit strings; Efficiency
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 (1MB) | Preview

Abstract

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.

More information

Item ID: 33261
DC Identifier: http://oa.upm.es/33261/
OAI Identifier: oai:oa.upm.es:33261
Official URL: http://link.springer.com/chapter/10.1007%2F978-3-319-00651-2_16
Deposited by: Memoria Investigacion
Deposited on: 02 Feb 2015 11:58
Last Modified: 10 Oct 2018 09:02
  • 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