https://hal-utt.archives-ouvertes.fr/hal-02291646de Noronha, Thiago FerreiraThiago Ferreirade NoronhaUFMG - Universidade Federal de Minas Gerais [Belo Horizonte]Ribeiro, CelsoCelsoRibeiroUFF - Universidade Federal Fluminense [Rio de Janeiro]Santos, Andréa CynthiaAndréa CynthiaSantosLOSI - Laboratoire d'Optimisation des Systèmes Industriels - ICD - Institut Charles Delaunay - UTT - Université de Technologie de Troyes - CNRS - Centre National de la Recherche ScientifiqueSolving diameter-constrained minimum spanning tree problems by constraint programmingHAL CCSD2010constraint programmingdiameter constrained spanning treesbounded-diameterSpanning trees[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]VU VAN, Jean-Baptiste2019-09-19 09:56:042023-03-24 14:53:122019-09-19 09:56:04enJournal articles10.1111/j.1475-3995.2010.00780.x1The diameter‐constrained minimum spanning tree problem consists in finding a minimum spanning tree of a given graph, subject to the constraint that the maximum number of edges between any two vertices in the tree is bounded from above by a given constant. This problem typically models network design applications where all vertices communicate with each other at a minimum cost, subject to a given quality requirement. We propose alternative formulations using constraint programming that circumvent weak lower bounds yielded by most mixed‐integer programming formulations. Computational results show that the proposed formulation, combined with an appropriate search procedure, solves larger instances and is faster than other approaches in the literature.