A linear ordering consists in arranging the vertices of the graph in a horizontal line. Mathematically, a linear ordering is the one-to-one mapping function , where is the set of vertices and is the number of vertices in the graph. In the linear ordering , the vertex is placed at the first position, the vertex at the second position and so on.
Published in Chapter:
Optimization of the Vertex Separation Problem with Genetic Algorithms
Héctor J. Fraire Huacuja (Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero, Mexico) and Norberto Castillo-García (Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero, Mexico)
Copyright: © 2016
|Pages: 19
DOI: 10.4018/978-1-4666-9779-9.ch002
Abstract
The Vertex Separation Problem (VSP) is an NP-hard combinatorial optimization problem in the context of graph theory. The importance of studying VSP lies in its close relation with other problems. Thus, VSP has important practical applications in the contexts of very large scale integration design, computer language compiler design, natural language processing, order processing of manufactured products and bioinformatics. Up to our knowledge, there are only two trajectory-based metaheuristic algorithms for VSP documented in the literature. The main contribution of this chapter is that we extend the available heuristics to solve VSP by proposing a genetic algorithm (GA). It is of particular interest to study the impact of four different crossover operators in the algorithm performance. The experimental results showed that the order-based crossover is the best. Moreover, the best GA variant was compared with the best algorithm for VSP: GVNS. The results of this comparison showed that GVNS outperforms our best GA variant by approximately 1.54 times in solution quality.