The Hop-constrained Minimum Spanning Tree Problem (HMST) is defined as fol-lows: Given a graph G = (V, E) with node set V = {0, 1, . . . , n}, edge set E as well as a cost c e associated with each edge e ∈ E and a natural number H, we wish to find a spanning tree T of the graph with minimum total cost such that the unique path from a specified root node, node 0, to any other node has no more than H hops (edges). The HMST is N P-hard because it contains as a particular case (the case with H = 2) an N P-hard version of the simple uncapacitated facility location problem (see [6, 2]). It has been shown by [11] that the HMST is even not in APX, i.e., the class of problems for which it is possible to have polynomial time heuristics with a guaranteed approximation bound. The HMST models the design of centralized telecommunication networks with quality of service constraints. The root node represents the site of a central processor (computer) and the remaining nodes represent terminals that are required to be linked to the central processor. The hop constraints limit the number of hops (edges) between the root node and any other node and guarantee a certain level of service with respect to some performance constraints such as availability and reliability (see, e.g., [15]). Availability refers to the probability that all the transmission lines in the path from the root node to the terminal are working, and reliability corresponds with the probability that a session will not be interrupted by a link failure. In general, these probabilities decrease with the number of links in the path implying that paths with fewer hops have a better performance with respect to availability and reliability. Centralized terminal networks are also usually implemented with multidrop lines for connecting the termi-nals with the center. In such networks, node processing times dominate over queuing delays and fewer hops mean, in general, lower delays.