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 SizeFormat 
G12072016_donacion_tesis_bib.pdf1.64 MBAdobe PDFView/Open


This item is protected by original copyright



This item is licensed under a Creative Commons License Creative Commons