Por favor, use este identificador para citar o enlazar este ítem:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3092| Título : | METODOS EXACTOS PARA EL PROBLEMA DEL SUMCUT DE UN GRAFO CONEXO NO DIRIGIDO |
| Autor : | Gomez Rojas, Yazmin |
| Fecha de publicación : | 2014-10-01 |
| Editorial : | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Instituto Tecnológico de Ciudad Madero |
| Descripción : | En este trabajo de investigación aborda el problema de SUMCUT por medio de métodos exactos. El SUMCUT es un problema NP-Completo [Yuan, 1998], el cual consiste en minimizar la suma de los cortes de ancho de un grafo conexo; este problema tiene aplicaciones en la genética y en la arqueología [Karp, 1993] [Kendall, 1993]. La aportación de este trabajo consiste en el desarrollo de 4 modelos de programación lineal entera y 2 métodos exactos basados en ramificación y acotamiento, ya que hasta el momento no se han publicado ningún método exacto que lo resuelva. Además se realizó una heurística para crear una solución inicial, la cual permitiera trabajar con las instancias con un gran número de nodos. Para validar la eficiencia de la heurística se realizó una metaheurística GRASP. |
| metadata.dc.type: | info:eu-repo/semantics/masterThesis |
| Aparece en las colecciones: | Maestría en Ciencias de la Computación |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| G07070938_donacion_tesis_bib.pdf | 2.26 MB | Adobe PDF | Visualizar/Abrir |
Este ítem está protegido por copyright original |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons
