Reload cost problems: Minimum diameter spanning tree (Q5948962)

This paper is concerned with a special optimization problem on an edge-colored graph. Given a reload cost function on pairs of colours, reload cost distance is defined for a path of the graph. The problem is to find a spanning tree of the graph such that the path with maximal reload cost distance (diameter) is minimized on all spanning trees. Computational complexity results are presented for the general problem case with cost function satisfying the triangle inequality and for graphs of degree 5. The authors also present an exact algorithm for graphs with maximum degree 3 and triangle inequality condition. The algorithm is based on the idea to map the graph with reload costs to an equivalent edge-weighted graph and then to use the known algorithms for minimum diameter spanning trees. Overall, this paper contains valuable original results which probably have not been presented in literature so far.