1. Repositorio Institucional del Tecnológico Nacional de México (RI - TecNM)
2. Tesis de Posgrado
3. Tamaulipas
4. Instituto Tecnológico de Ciudad Madero
5. Tesis
6. Tesis de Maestría
7. Maestría en Ciencias de la Computación

Título :	Métodos exactos para el problema de la bisección de vértices de un grafo conexo no dirigido
Autor :	Rodriguez Del Angel, Eduardo
Fecha de publicación :	2014-11-01
Editorial :	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Instituto Tecnológico de Ciudad Madero
Descripción :	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
Aparece en las colecciones:	Maestría en Ciencias de la Computación

Este ítem está protegido por copyright original Visualizar la licencia

Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons