Cálculo de separadores de grafos utilizando búsqueda de vecindad variable reducida

Resumen

Dado un grafo conexo y no dirigido G = (V, E) y un lími-te entero positivo b, el problema del Vertex Separator (VS) consiste en encontrar el conjunto de vértices C, que eliminado divide G en com-ponentes aisladas A, B, donde max(|A|, |B|) ≤ b. Este es un problema de optimización NP-completo y puede ser utilizado en un amplio rango de aplicaciones. Por ejemplo, en redes de telecomunicaciones un separa-dor determina la capacidad y fragilidad de la red. En el campo de los algoritmos para grafos, el cálculo de pequeños separadores balanceados es mu util, especialmente en los algoritmos del tipo divide y vencerás. Este trabajo presenta un nuevo algoritmo heurístico basado en el méto-do Variable Neighborhood Search (VNS) para el cálculo de separadores. El método es comparado con el estado del arte (dos procedimientos de ramificación y poda recientes). Los resultados muestran que el método obtiene la solució optima en todas las instancias pequeñas y medianas, y obtiene buenos resultados en instancias grandes. Aunque los métodos anteriores aseguran encontrar la solució optima, tienen un tiempo de ejecución mucho mayor que el método presentado (aunqué este no ase-gura que la solución obtenida sea lá optima)

Jesús Sánchez-Oro

Profesor Titular de Universidad

Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.

Abraham Duarte

Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.