Metaheurística GRASP para el problema Vertex Bisection Minimization

Abstract

Dado un grafo no orientado G = (V, E), donde V denota el conjunto de vértices y E representa el conjunto de aristas, el problema Vertex Bisection Minimization consiste en particionar el conjunto V en dos subconjuntos B y Bt , de manera que |B| = ||V |/2J y se minimice el número de vértices en B que son adyacentes a algún vértice de Bt . Este problema pertenece al conjunto de los problemas de diseño de grafos y tiene aplicaciones en áreas como optimización de redes, teoría de grafos, recuperación de información, etc. Este problema es NP-difícil sobre grafos en general, aunque polinomialmente soluble para árboles e hipercubos. Por su importancia, diversos enfoques heurísticos han sido realizados con el propósito de encontrar soluciones de calidad. En este trabajo fue desarrollada una metaheurística GRASP para abordar este problema. Los resultados experimentales muestran que el algoritmo propuesto obtiene resultados de mejor calidad que los algoritmos heurísticos encontrados en la literatura para este problema.

Given a non-oriented graph G = (V, E), where V denotes the set of vertices and E represents the set of edges, the Vertex Bisection Minimization problem consists of partitioning V into two subsets B and B t , such that |B| =||V |/2J and minimizing the number of vertices in B that are adjacent to some vertex of Bt . This problem belongs to the set of graph layout problems and has applications in areas such as network optimization, graph theory, information retrieval, etc. This problem is NP-hard on graphs in general, but polynomially soluble for trees and hypercubes. Because of its importance, various heuristic approaches have been carried out with the purpose of finding quality solutions. In this work, a GRASP metaheuristics was developed to address this problem. The experimental results show that the proposed algorithm obtains better quality results than the heuristic algorithms found in the literature for this problem.