Online coloring in optical networks

The problem is defined as follows. Given a network modeled as a graph
G = (V, E) and a set of lightpaths {p_1, p_2, ..., p_n}, the problem is
to assign a color to each lightpath such that any two paths sharing
the same edge are given different colors. Each lightpath needs to use
two ADMs (Add-Drop-Multiplexers), one at each end. If two lightpaths
of the same color shares the same end point, they can share one ADM,
thus saving one ADM. The objective is to assign colors to lightpaths
to minimize the total number of ADMs used. Results in the online setting
will be presented on various graph topologies.

This is joint work with Mordechai Shalom and Shmuel Zaks.