The Minimum Routing Cost Tree Problem State of the art and a core-node based heuristic algorithm

The minimum routing cost tree problem arises when we need to find the tree minimizing the minimum travel/communication cost, i.e., the tree which presents the minimal difference with the same cost computed on the whole network. This paper provides the state of the art of the problem and proposes a new heuristic based on the identification of a core of the network around which the solution can be built. The algorithm has been tested on literature instances of up to one thousand nodes. The results, compared with those of other heuristic algorithms, prove the competitiveness of the proposed one both in terms of the quality of the solution and computation time.