Utilize este identificador para referenciar este registo:
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 |
| Data: | 2014-10-01 |
| Editora: | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Instituto Tecnológico de Ciudad Madero |
| Descrição: | 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 nas colecções: | Maestría en Ciencias de la Computación |
Ficheiros deste registo:
| Ficheiro | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| G07070938_donacion_tesis_bib.pdf | 2.26 MB | Adobe PDF | Ver/Abrir |
Este registo está protegido por copyright original. |
Este registo está protegido por Licença Creative Commons
