Veuillez utiliser cette adresse pour citer ce document :
https://rinacional.tecnm.mx/jspui/handle/TecNM/3092| Titre: | METODOS EXACTOS PARA EL PROBLEMA DEL SUMCUT DE UN GRAFO CONEXO NO DIRIGIDO |
| Auteur(s): | Gomez Rojas, Yazmin |
| Date de publication: | 2014-10-01 |
| Editeur: | 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 |
| Collection(s) : | Maestría en Ciencias de la Computación |
Fichier(s) constituant ce document :
| Fichier | Description | Taille | Format | |
|---|---|---|---|---|
| G07070938_donacion_tesis_bib.pdf | 2.26 MB | Adobe PDF | Voir/Ouvrir |
Ce document est protégé par copyright |
Ce document est autorisé sous une licence de type Licence Creative Commons
