Preliminary results on an extension of the vertex cover problem

J. F. Correcher, M. Landete, J. Peiró, H. Yaman

In some contexts, we can model the relationship between locations and their connections using some extensions of the vertex cover problem. In this talk, we revisit some of these extensions, provide preliminary results that can be used for solutions methods, and connect them with well-known polyhedra such as the boolean quadric polytope. We present computational results from a branch-and-cut algorithm in which we show the applicability of our proposals.

Keywords: vertex cover, boolean quadric polytope, valid inequalities, exact method

GT12.GELOCA1 Invited Session
November 9, 2023  3:30 PM
HC2: Canónigos Room 2

V. Blanco

M. Landete, J. M. Munoz Ocana, A. M. Rodríguez Chía, F. Saldanha-da-Gama

J. L. Sainz-Pardo Auñón, J. Valero Cuadra