Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3092| Title: | METODOS EXACTOS PARA EL PROBLEMA DEL SUMCUT DE UN GRAFO CONEXO NO DIRIGIDO |
| Authors: | Gomez Rojas, Yazmin |
| Issue Date: | 2014-10-01 |
| Publisher: | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Instituto Tecnológico de Ciudad Madero |
| Description: | 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 |
| Appears in Collections: | Maestría en Ciencias de la Computación |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| G07070938_donacion_tesis_bib.pdf | 2.26 MB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
