Two New Exact Methods for the Vertex Separation Problem

  • Héctor J. Fraire Huacuja Tecnológico Nacional de México. Instituto Tecnológico de Ciudad Madero
  • Norberto Castillo-García Tecnológico Nacional de México. Instituto Tecnológico de Ciudad Madero
  • Rodolfo A. Pazos Rangel Tecnológico Nacional de México. Instituto Tecnológico de Ciudad Madero
  • José Antonio Martínez Flores Tecnológico Nacional de México. Instituto Tecnológico de Ciudad Madero
  • Juan Javier González Barbosa Tecnológico Nacional de México. Instituto Tecnológico de Ciudad Madero
  • Juan Martín Carpio Valadez Tecnológico Nacional de México. Instituto Tecnológico de León
Keywords: Combinatorial Optimization, Vertex Separation Problem, Branch and Bound Algorithm, Integer Linear Programming Formulation

Abstract

The Vertex Separation Problem (VSP) is an NP-hard combinatorial optimization problem in the context of graph theory. Particularly, VSP belongs to a family of linear ordering problems in which the goal is to find the best separator of vertices in a generic graph. In the literature reviewed, we only found two exact methods based on integer linear programming (IP) formulations. The main contribution of this paper is that we have extended the available exact methods by proposing an ad hoc branch and bound algorithm (BBVSP) and a new IP formulation (IPVSP). The experimental results show that BBVSP is the best method since it found the largest number of optimal solutions and achieved the lowest computing time. More precisely, BBVSP found 100 optimal values out of 108 instances evaluated, which represents an effectiveness of 92.6%. BBVSP also achieves a saving of time of about 91.1% with respect to the best exact IP formulation found in the literature.

Published
2015-01-18
How to Cite
Fraire Huacuja, H., Castillo-García, N., Pazos Rangel, R., Martínez Flores, J., González Barbosa, J., & Carpio Valadez, J. (2015). Two New Exact Methods for the Vertex Separation Problem. International Journal of Combinatorial Optimization Problems and Informatics, 6(1), 31-41. Retrieved from https://ijcopi.org/index.php/ojs/article/view/60
Section
Articles