Thiessen, M.M.ThiessenQuesada, L.L.QuesadaBrown, K.N.K.N.Brown2022-03-142022-03-142020https://publica.fraunhofer.de/handle/publica/41000610.1007/978-3-030-58942-4_29The degree-constrained minimum spanning tree problem, which involves finding a minimum spanning tree of a given graph with upper bounds on the vertex degrees, has found multiple applications in several domains. In this paper, we propose a novel CP approach to tackle this problem where we extend a recent branch-and-bound approach with an adaptation of the LKH local search heuristic to deal with trees instead of tours. Every time a solution is found, it is locally optimised by our new heuristic, thus yielding a tightened cut. Our experimental evaluation shows that this significantly speeds up the branch-and-bound search and hence closes the performance gap to the state-of-the-art bottom-up CP approach.en005006629conference paper