Full text
![[img]](http://oa.upm.es/style/images/fileicons/application_pdf.png) |
PDF
- Users in campus UPM only
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (257kB) |
Reusing the same coloring in the child nodes of the search tree for the maximum clique problem
Citation
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: |
|
| 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 |
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 |
