Resumen

El problema del Particionado de Grafos (gpp—Graph Partitioning Problem) es un problema NP-Difícil cuyo objetivo es particionar los nodos de un grafo en k conjuntos de forma que se minimice el número de aristas que unen vértices localizados en diferentes conjuntos, a la vez que se cumplen restricciones relativas al tamaño de los conjuntos. En los últimos años, el desarrollo de metaheurísticas poblacionales que incorporan un control explícito de la diversidad ha permitido realizar avances significativos al tratar diversos problemas de optimización combinatoria como el problema de coloreado de grafos o el de asignación de frecuencias. A pesar de que el gpp es un problema clásico, el desarrollo de metaheurísticas poblacionales con control de diversidad para el gpp es un tema prácticamente inexplorado. Por ello, a partir de la hipótesis de que un algoritmo memético con gestión de diversidad ayudaría a mejorar el estado del arte para el gpp, se desarrollaron nuevos algoritmos que efectivamente han permitido mejorar las soluciones encontradas hasta la fecha para una gran cantidad de casos. El trabajo presentado es un resumen de la tesis que ganó el Premio Mixbaal a la mejor tesis de licenciatura en matemáticas aplicadas, en la edición del año 2019. Este premio es otorgado por la Sociedad Mexicana de Computación Científica y Sus Aplicaciones.

Documento

The PDF file did not load properly or your web browser does not support viewing PDF files. Download directly to your device: Download PDF document
Back to Top
GET PDF

Document information

Published on 14/12/19
Submitted on 30/11/19

Licence: CC BY-NC-SA license

Document Score

0

Views 14
Recommendations 0

Share this document

claim authorship

Are you one of the authors of this document?