Spanning Cover Inequalities for the Capacitated Vehicle Routing Problem - Arcencio, Guilherme G.; Mattioli, Matheus T.; Hokama, Pedro H. D. B.; San Felice, Mário César (Anais do Encontro de Teoria da Computação (ETC); 2021: Anais do VI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2021.16387, 2021)
In the k-Minimum Spanning Subgraph problem with d-Degree Center we want to find a minimum cost spanning connected subgraph with n - 1 + k edges and at least degree d in the center vertex, with n being the number of vertices. In this paper we describe an algorithm for this problem and present correctness demonstrations which we believe are simpler than those found in the literature. A solution for the k-Minimum Spanning Subgraph problem with d-Degree can be used to formulate spanning cover inequalities for the capacitated vehicle routing problem.