%A Arcencio, Guilherme G.
%A Mattioli, Matheus T.
%A Hokama, Pedro H. D. B.
%A San Felice, Mário César
%D 2021
%T Spanning Cover Inequalities for the Capacitated Vehicle Routing Problem
%K
%X 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.
%U https://sol.sbc.org.br/index.php/etc/article/view/16387
%J Anais do Encontro de Teoria da Computação (ETC)
%0 Journal Article
%R 10.5753/etc.2021.16387
%P 86-89%@ 2595-6116
%8 2021-07-18