Minimum Diameter Trees Subject to a Budget Constraint - Azevedo, Amanda Ferreira de; Lucena, Abilio (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
Formulations are proposed for problems that ask for minimum diameter trees of an undirected graph, subject to an upper bound on the sum of their edge costs. The problems, namely the Budget Restricted Minimum Diameter Spanning Tree, the Budget Restricted Minimum Diameter Steiner Tree, and the Budget Restricted Minimum Diameter Terminal Steiner Tree, represent challenging extensions for three intensively investigated NP-hard problems. Furthermore practical applications for these extensions naturally carry over from those for the problems they originate from. Three distinct types of formulations are proposed here for each of the previously indicated problem extensions. Computational results for these formulations will be presented separately.