TY - JOUR
AU - Arcencio, Guilherme G.
AU - Mattioli, Matheus T.
AU - Hokama, Pedro H. D. B.
AU - San Felice, Mário César
PY - 2021/07/18
TI - Spanning Cover Inequalities for the Capacitated Vehicle Routing Problem
JF - Anais do Encontro de Teoria da Computação (ETC); 2021: Anais do VI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2021.16387
KW -
N2 - 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.
UR - https://sol.sbc.org.br/index.php/etc/article/view/16387