Reusing the same coloring in the child nodes of the search tree for the maximum clique problem

Nikolaev, Alexey and Batsyn, Mikhail and San Segundo Carrillo, Pablo (2015). Reusing the same coloring in the child nodes of the search tree for the maximum clique problem. In: "Learning and Intelligent Optimization Conference: LION 9", 12/01/2015-15/01/2015, Lille, France. ISBN 978-3-319-19084-6. pp. 275-280.

Description

Title: Reusing the same coloring in the child nodes of the search tree for the maximum clique problem
Author/s:
  • Nikolaev, Alexey
  • Batsyn, Mikhail
  • San Segundo Carrillo, Pablo
Item Type: Presentation at Congress or Conference (Article)
Event Title: Learning and Intelligent Optimization Conference: LION 9
Event Dates: 12/01/2015-15/01/2015
Event Location: Lille, France
Title of Book: Learning and Intelligent Optimization: 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers
Date: January 2015
ISBN: 978-3-319-19084-6
Volume: 8994
Subjects:
Freetext Keywords: Maximum clique problem; Branch-and-bound algorithm; Reusing coloring
Faculty: E.T.S.I. Diseño Industrial (UPM)
Department: Ingeniería Eléctrica, Electrónica Automática y Física Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (257kB)

Abstract

In this paper we present a new approach to reduce the computational time spent on coloring in one of the recent branch-and-bound algorithms for the maximum clique problem. In this algorithm candidates to the maximum clique are colored in every search tree node. We suggest that the coloring computed in the parent node is reused for the child nodes when it does not lead to many new branches. So we reuse the same coloring only in the nodes for which the upper bound is greater than the current best solution only by a small value Δ. The obtained increase in performance reaches 70% on benchmark instances.

More information

Item ID: 42060
DC Identifier: http://oa.upm.es/42060/
OAI Identifier: oai:oa.upm.es:42060
Official URL: http://www.lifl.fr/LION9/
Deposited by: Memoria Investigacion
Deposited on: 01 Jul 2016 07:24
Last Modified: 06 Jul 2016 07:10
  • 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