Texto completo
![[thumbnail of INVE_MEM_2015_225432.pdf]](https://oa.upm.es/style/images/fileicons/application_pdf.png) |
PDF (Portable Document Format)
- Acceso permitido solamente a usuarios en el campus de la UPM
- Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (257kB) |
Reusing the same coloring in the child nodes of the search tree for the maximum clique problem
Cita
Nikolaev, Alexey, Batsyn, Mikhail and San Segundo Carrillo, Pablo 
ORCID: https://orcid.org/0000-0001-7050-5563
(2015).
Reusing the same coloring in the child nodes of the search tree for the maximum clique problem.
En: "Learning and Intelligent Optimization Conference: LION 9", 12/01/2015-15/01/2015, Lille, France. ISBN 978-3-319-19084-6. pp. 275-280.
ORCID: https://orcid.org/0000-0001-7050-5563
(2015).
Reusing the same coloring in the child nodes of the search tree for the maximum clique problem.
En: "Learning and Intelligent Optimization Conference: LION 9", 12/01/2015-15/01/2015, Lille, France. ISBN 978-3-319-19084-6. pp. 275-280.
Descripción
| Título: | Reusing the same coloring in the child nodes of the search tree for the maximum clique problem |
|---|---|
| Autor/es: |
|
| Tipo de Documento: | Ponencia en Congreso o Jornada (Artículo) |
| Título del Evento: | Learning and Intelligent Optimization Conference: LION 9 |
| Fechas del Evento: | 12/01/2015-15/01/2015 |
| Lugar del Evento: | Lille, France |
| Título del Libro: | Learning and Intelligent Optimization: 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers |
| Fecha: | Enero 2015 |
| ISBN: | 978-3-319-19084-6 |
| Volumen: | 8994 |
| Materias: | |
| ODS: | |
| Palabras Clave Informales: | Maximum clique problem; Branch-and-bound algorithm; Reusing coloring |
| Escuela: | E.T.S.I. Diseño Industrial (UPM) |
| Departamento: | Ingeniería Eléctrica, Electrónica Automática y Física Aplicada |
| Licencias Creative Commons: | Reconocimiento - Sin obra derivada - No comercial |
Resumen
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.
Más información
| ID de Registro: | 42060 |
|---|---|
| Identificador DC: | https://oa.upm.es/42060/ |
| Identificador OAI: | oai:oa.upm.es:42060 |
| URL Oficial: | http://www.lifl.fr/LION9/ |
| Depositado por: | Memoria Investigacion |
| Depositado el: | 01 Jul 2016 07:24 |
| Ultima Modificación: | 25 Ene 2023 12:28 |
Acciones
- Estadísticas
- Exportar cita
- Editar (sólo personal del Archivo)
