Line System Design and a Generalized Coloring Problem

We study a generalized coloring and routing problem for interval and circular graphs that is motivated by design of optical line systems. In this problem we are interested in finding a coloring (wavelength assignment) and routing (for circular graphs) of "demands" of minimum total cost where the total cost is obtained by accumulating the cost incurred at certain "links" (amplifier locations) in the graph.