Complexity of edge coloring with minimum reload/changeover costs

Abstract

In an edge-colored graph, a traversal cost occurs along a path when consecutive edges with different colors are traversed. The value of the traversal cost depends only on the colors of the edges. Two related global cost measures, namely the reload cost and the changeover cost with applications in telecommunications, transportation networks, and energy distribution networks have been studied in the literature. Previous work focused on problems with an edge-colored graph being part of the input. In this paper, we formulate problems that aim to find an edge coloring of a graph minimizing the reload and changeover costs. One pair of problems aims to find a proper edge coloring to minimize the reload/changeover cost of a set of paths. Another pair of problems aim to find a proper edge coloring and a spanning tree to minimize the reload/changeover cost. We present several hardness results and polynomial-time solvable special cases.