Open AccessSpanning Cover Inequalities for the Capacitated Vehicle Routing Problem
Author(s) -
Guilherme G. Arcencio,
Matheus T. Mattioli,
Pedro Henrique Del Bianco Hokama,
Mário César San Felice
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/etc.2021.16387
Subject(s) - correctness , combinatorics , degree (music) , minimum degree spanning tree , routing (electronic design automation) , cover (algebra) , vehicle routing problem , mathematics , vertex (graph theory) , computer science , spanning tree , discrete mathematics , graph , algorithm , engineering , computer network , mechanical engineering , physics , acoustics
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.