TY - JOUR AU - Fraire Huacuja, Héctor J. AU - Castillo-García, Norberto AU - Pazos Rangel, Rodolfo A. AU - Martínez Flores, José Antonio AU - González Barbosa, Juan Javier AU - Carpio Valadez, Juan Martín PY - 2015/01/18 Y2 - 2024/03/29 TI - Two New Exact Methods for the Vertex Separation Problem JF - International Journal of Combinatorial Optimization Problems and Informatics JA - Int. Journal of COP and Infor. VL - 6 IS - 1 SE - Articles DO - UR - https://ijcopi.org/ojs/article/view/60 SP - 31-41 AB - <p>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.</p> ER -