Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3090| Title: | Métodos exactos para el problema de la bisección de vértices de un grafo conexo no dirigido |
| Authors: | Rodriguez Del Angel, Eduardo |
| Issue Date: | 2014-11-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 se abordó el problema de bisección de vértices de un grafo conexo no dirigido mediante métodos exactos. Este problema pertenece a la clase NP-duro y consiste en separar a los nodos de un grafo en dos subconjuntos del mismo tamaño (izquierda y derecha), de tal manera que se minimice la cantidad de vértices en el conjunto izquierdo que tengan al menos una arista que lo conecte al conjunto derecho. Las contribuciones más importantes del trabajo son un modelo de programación lineal entera (ILP2) y un algoritmo enumerativo basado en combinaciones que aprovecha la estructura del problema para delimitar el espacio de soluciones. Se realizaron pruebas experimentales para estos algoritmos y para otros dos métodos de solución propuestos, en estas pruebas se utilizaron 108 instancias estándar para problemas de ordenamiento lineal. El modelo de programación ILP2 obtuvo 99 soluciones óptimas lo cual corresponde a un 91.67%. El método enumerativo por combinaciones obtuvo 103 soluciones óptimas lo cual corresponde a un 95.37%. Ambos programas fueron sujetos a los mismos parámetros de tiempo para cada uno de los experimentos. Los resultados parciales de este trabajo se incorporaron en un artículo titulado “Exact Methods for the Vertex Bisection Problem”, el cual fue publicado en el libro “Recent Advances on Hybrid Approaches for Designing Intelligent Systems, Studies in Computational Intelligence”. Palabras clave: Bisección de vértices, métodos exactos, branch and bound, programación lineal entera. |
| 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 | |
|---|---|---|---|---|
| G12072016_donacion_tesis_bib.pdf | 1.64 MB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
