A New Heuristic for the Minimum Routing Cost Spanning Tree Problem

Given a connected, weighted, and undirected graph, the minimum routing cost spanning tree problem seeks on this graph a spanning tree of minimum routing cost, where routing cost is defined as the sum of the costs of all the paths connecting two distinct vertices in a spanning tree. In this paper we have proposed a perturbation based local search for this problem. We have compared our approach against three methods reported in the literature - two genetic algorithms and a stochastic hill climber.Computational results show the effectiveness of our approach.