Premium
Complexity of edge coloring with minimum reload/changeover costs
Author(s) -
Gözüpek Didem,
Shalom Mordechai
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21867
Subject(s) - changeover , tree traversal , computer science , edge coloring , enhanced data rates for gsm evolution , graph , graph traversal , mathematical optimization , fractional coloring , mathematics , algorithm , theoretical computer science , telecommunications , line graph , graph power , transmission (telecommunications)
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.