| Revista: | Computación y sistemas |
| Base de datos: | |
| Número de sistema: | 000560139 |
| ISSN: | 1405-5546 |
| Autores: | Romero Ruiz, Emmanuel1 Segura, Carlos2 |
| Instituciones: | 1Universidad de Guanajuato, Guanajuato. México 2Centro de Investigación en Matemáticas, Guanajuato. México |
| Año: | 2018 |
| Periodo: | Abr-Jun |
| Volumen: | 22 |
| Número: | 2 |
| Paginación: | 347-361 |
| País: | México |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Resumen en inglés | The Graph Partitioning Problem (GPP) is a well-known NP-hard combinatorial problem that involves the finding of a partition of vertexes that minimizes the number of cut edges while fulfilling a set of constraints. This paper presents a newly designed optimizer for the GPP: the Memetic Algorithm with Hungarian Matching Based Crossover and Diversity Preservation (MAHMBCDP). MAHMBCDP is a population-based scheme that incorporates an explicit mechanism to control the diversity with the aim of making a proper use of resources when dealing with long-term executions. Among the novelties of our proposal, the design of a crossover operator that is based on the Hungarian Algorithm to calculate a maximum matching is particularly important. Experimental validation with a set of well-known instances of the graph partitioning archive shows the proper performance of our proposal. In fact, new best-known solutions could be attained in ten test cases. |
| Disciplinas: | Ciencias de la computación |
| Palabras clave: | Procesamiento de datos, Redes, Partición de gráficos, Algoritmo memético, Preservación de la diversidad, Coincidencia máxima |
| Keyword: | Graph partitioning, Memetic algorithm, Diversity preservation, Maximum matching, Data processing, Networks |
| Texto completo: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
