Determining hop-constrained spanning trees with repetitive heuristics

Abstract

The hop-constrained minimum spanning tree problem is the problem of determining a rooted spanning tree of minimum cost in which each path from the root node to any other node contains at most H hops or edges. This problem relates to the design of centralized tree networks with quality of service requirements (in telecommunications) and has a close relation with other tree problems. In this paper we investigate the adaptation of some well-known "repetitive" heuristics used for the capacitated minimum spanning tree problem to the hop-constrained minimum spanning tree problem and investigate some simple look ahead mechanisms for enhancing the quality of a savings heuristic. Computational results for a set of benchmark tests with up to 80 nodes are presented.