Por favor, use este identificador para citar o enlazar este ítem: https://repositorio.uci.cu/jspui/handle/123456789/9492
Título : Metaheurística GRASP para el problema Vertex Bisection Minimization
Otros títulos : GRASP metaheuristics for the Vertex Bisection Minimization problem
Autor : Moreno Ramírez, Jorge
Palabras clave : METAHEURISTICA;GRASP;BISECCION DE VERTICES
Fecha de publicación : 2018
Editorial : Ediciones Futuro
Citación : Moreno, J. (2018). Metaheurística GRASP para el problema Vertex Bisection Minimization. Revista Cubana de Ciencias Informáticas. Vol. 12(2018) : Especial UCIENCIA, pp. 28-41. Recuperado de https://rcci.uci.cu/?journal=rcci&page=article&op=view&path%5B%5D=1791
Resumen : 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.
URI : https://repositorio.uci.cu/jspui/handle/123456789/9492
ISSN : 2227.1899
Aparece en las colecciones: Eventos

Ficheros en este ítem:
Fichero Tamaño Formato  
215.pdf115.22 kBAdobe PDFVisualizar/Abrir


Los ítems del Repositorio están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.