文章基本信息

标题：Two New Exact Methods for the Vertex Separation Problem
本地全文：下载
作者：Héctor J. Fraire Huacuja ; Norberto Castillo—García ; Rodolfo A. Pazos Rangel 等
期刊名称：International Journal of Combinatorial Optimization Problems and Informatics
印刷版ISSN：2007-1558
电子版ISSN：2007-1558
出版年度：2015
卷号：6
期号：1
页码：31-41
语种：English
出版社：International Journal of Combinatorial Optimization Problems and Informatics
其他摘要：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.
其他关键词：Combinatorial Optimization; Vertex Separation Problem; Branch and Bound Algorithm; Integer Linear Programming Formulation.