Cover Image

A fast genetic algorithm for the Maximum Cut-Clique problem.

En esta tesis se presenta un problema reciente de teoría de grafos conocido como Máximo Clique-Corte o MCC. Dado un grafo simple, se desea hallar un subgrafo completo tal que el corte inducido por sus nodos tenga máximo cardinal. Este problema combinatorio fue introducido por P. Martins en 2012, y e...

Full description

Saved in:
Main Author: Fortez Hitateguy, Giovanna Elizabeth (author)
Format: masterThesis
Language:Spanish
Published: 2019
Subjects:
Optimización
Máximo Clique-Corte
Metaheurísticas
Algoritmos Genéticos
Online Access:https://hdl.handle.net/20.500.12008/50011
Tags: Add Tag
No Tags, Be the first to tag this record!
_version_ 1868890025106604032
author Fortez Hitateguy, Giovanna Elizabeth
author_browse Fortez Hitateguy, Giovanna Elizabeth
author_facet Fortez Hitateguy, Giovanna Elizabeth
author_role author
collection COLIBRI
dc.contributor.none.fl_str_mv Fortez Hitateguy Giovanna Elizabeth, Universidad de la República (Uruguay). Facultad de Ingeniería.
dc.creator.none.fl_str_mv Fortez Hitateguy, Giovanna Elizabeth
dc.date.none.fl_str_mv 2019
2025-05-14T15:38:29Z
2025-05-14T15:38:29Z
dc.format.none.fl_str_mv 75 p.
application/pdf
dc.identifier.none.fl_str_mv Fortez Hitateguy, G. A fast genetic algorithm for the Maximum Cut-Clique problem [en línea] Tesis de maestría. Montevideo : Udelar. FI. INCO, 2019.
https://hdl.handle.net/20.500.12008/50011
dc.language.none.fl_str_mv es
spa
dc.publisher.none.fl_str_mv Udelar. FI.
dc.rights.none.fl_str_mv info:eu-repo/semantics/openAccess
Licencia Creative Commons Atribución (CC - By 4.0)
dc.source.none.fl_str_mv reponame:COLIBRI
instname:Universidad de la República
instacron:Universidad de la República
dc.subject.none.fl_str_mv Optimización
Máximo Clique-Corte
Metaheurísticas
Algoritmos Genéticos
dc.title.none.fl_str_mv A fast genetic algorithm for the Maximum Cut-Clique problem.
dc.type.none.fl_str_mv Tesis de maestría
info:eu-repo/semantics/masterThesis
info:eu-repo/semantics/acceptedVersion
description En esta tesis se presenta un problema reciente de teoría de grafos conocido como Máximo Clique-Corte o MCC. Dado un grafo simple, se desea hallar un subgrafo completo tal que el corte inducido por sus nodos tenga máximo cardinal. Este problema combinatorio fue introducido por P. Martins en 2012, y encuentra aplicaciones en el Análisis de Mercados, donde interesa la correlación de artículos de venta. La correspondiente versión de decisión del MCC pertenece a la categoría de problemas NP-Completos. Como consecuencia, los métodos exactos resultan computacionalmente prohibitivos para grafos de gran tamaño. En la literatura científica se dispone de heurísticas previas que explotan aleatoriedad con distintas estructuras de vecindad, como GRASP/VND o ILS. En esta tesis se presenta una nueva solución basada en Algoritmos Genéticos. Un estudio comparativo comprueba que la propuesta es altamente competitiva con trabajos anteriores, siendo su mayor fortaleza la eficiencia computacional.
eu_rights_str_mv openAccess
format masterThesis
id anni_45aa60fc280715c8388ee1fc3f9e4a7d
identifier_str_mv Fortez Hitateguy, G. A fast genetic algorithm for the Maximum Cut-Clique problem [en línea] Tesis de maestría. Montevideo : Udelar. FI. INCO, 2019.
instacron_str Universidad de la República
institution Universidad de la República
instname_str Universidad de la República
language spa
language_invalid_str_mv es
network_acronym_str anni
network_name_str oai-lr-anni
oai_identifier_str oai:colibri.udelar.edu.uy:20.500.12008/50011
publishDate 2019
publishDateSort 2019
publisher.none.fl_str_mv Udelar. FI.
reponame_str COLIBRI
repository.mail.fl_str_mv
repository.name.fl_str_mv
repository_id_str
rights_invalid_str_mv Licencia Creative Commons Atribución (CC - By 4.0)
spelling A fast genetic algorithm for the Maximum Cut-Clique problem.Fortez Hitateguy, Giovanna ElizabethOptimizaciónMáximo Clique-CorteMetaheurísticasAlgoritmos GenéticosEn esta tesis se presenta un problema reciente de teoría de grafos conocido como Máximo Clique-Corte o MCC. Dado un grafo simple, se desea hallar un subgrafo completo tal que el corte inducido por sus nodos tenga máximo cardinal. Este problema combinatorio fue introducido por P. Martins en 2012, y encuentra aplicaciones en el Análisis de Mercados, donde interesa la correlación de artículos de venta. La correspondiente versión de decisión del MCC pertenece a la categoría de problemas NP-Completos. Como consecuencia, los métodos exactos resultan computacionalmente prohibitivos para grafos de gran tamaño. En la literatura científica se dispone de heurísticas previas que explotan aleatoriedad con distintas estructuras de vecindad, como GRASP/VND o ILS. En esta tesis se presenta una nueva solución basada en Algoritmos Genéticos. Un estudio comparativo comprueba que la propuesta es altamente competitiva con trabajos anteriores, siendo su mayor fortaleza la eficiencia computacional.Udelar. FI.Fortez Hitateguy Giovanna Elizabeth, Universidad de la República (Uruguay). Facultad de Ingeniería.2025-05-14T15:38:29Z2025-05-14T15:38:29Z2019Tesis de maestríainfo:eu-repo/semantics/masterThesisinfo:eu-repo/semantics/acceptedVersion75 p.application/pdfFortez Hitateguy, G. A fast genetic algorithm for the Maximum Cut-Clique problem [en línea] Tesis de maestría. Montevideo : Udelar. FI. INCO, 2019.https://hdl.handle.net/20.500.12008/50011reponame:COLIBRIinstname:Universidad de la Repúblicainstacron:Universidad de la RepúblicaesspaLas obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad de la República.(Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014)info:eu-repo/semantics/openAccessLicencia Creative Commons Atribución (CC - By 4.0)oai:colibri.udelar.edu.uy:20.500.12008/500112026-04-14T10:27:59Z
spellingShingle A fast genetic algorithm for the Maximum Cut-Clique problem.
Fortez Hitateguy, Giovanna Elizabeth
Optimización
Máximo Clique-Corte
Metaheurísticas
Algoritmos Genéticos
status_str acceptedVersion
title A fast genetic algorithm for the Maximum Cut-Clique problem.
title_full A fast genetic algorithm for the Maximum Cut-Clique problem.
title_fullStr A fast genetic algorithm for the Maximum Cut-Clique problem.
title_full_unstemmed A fast genetic algorithm for the Maximum Cut-Clique problem.
title_short A fast genetic algorithm for the Maximum Cut-Clique problem.
title_sort A fast genetic algorithm for the Maximum Cut-Clique problem.
topic Optimización
Máximo Clique-Corte
Metaheurísticas
Algoritmos Genéticos
url https://hdl.handle.net/20.500.12008/50011

Similar Items