Árvores de diâmetro mínimo sujeitas a restrição de orçamento

Abstract

Given an undirected graph G = (V, E), we investigate three problems seeking minimum diameter trees of G. The definition used for the diameter of a tree, T = (VT , ET ), is the usual one. Namely, the number of edges in the path of T that contains the largest number of them. For any of the three problems, costs are associated with the edges of G and the sum of the edge costs of a tree may not exceed a given budget value. For the first problem, the Budget Minimum Diameter Spanning Tree Problem, feasible trees must necessarily be spanning. For the second, the Budget Minimum Diameter Steiner Tree Problem, terminal vertices S ⊂ V are identified beforehand and must be part of any feasible tree. These trees, in turn, may be spanning or not. Finally, the third problem, the Budget Minimum Diameter Terminal Steiner Tree Problem, differs from the previous one in that it imposes a one-to-one relation between leaves of a tree and vertices of S. We propose what apparently are the very first formulations for any of the three problems. Three formulations for every problem. Next, we rely on the implicit enumeration algorithms of the solver Gurobi to obtain proven optimal solutions for any of them. Barely investigated in the literature, any of the three problems have practical application potential, particularly in the design of telecommunication networks. Additionally, they proved to be intrinsically interesting and defying, both in modelling and algorithmic terms.Também disponível on-line.