Constrained Bipartite Edge Coloring with Applications to Wavelength Routing
(ICALP'97)
Proceedings of the 24th International Colloquium on Automata,
Languages and Programming (ICALP'97),
LNCS 1256, Springer-Verlag, 1997, pp. 493-504.
Motivated by the problem of efficient routing in all-optical
networks, we study a constrained version of the bipartite edge coloring
problem. We show that if the edges adjacent to a pair of opposite vertices
of an L-regular bipartite graph are already colored with a*L different
colors, then the rest of the edges can be colored using at most (1+a/2)*L
colors. We also show that this bound is tight by constructing instances
in which (1+a/2)*L colors are indeed necessary. We also obtain tight
bounds on the number of colors that each pair of opposite vertices can
see.
Using the above results, we obtain a polynomial time greedy algorithm
that assigns proper wavelengths to a set of requests of maximum load
L per directed fiber link on a directed fiber tree using at most 5L/3
wavelengths. This improves previous results of Raghavan and Upfal (1991),
Mihail, Kaklamanis, and Rao (1995), Kaklamanis and Persiano (1996), and
Kumar and Schwabe (1997).
We also obtain that no greedy algorithm can in general use less than
5L/3 wavelengths for a set of requests of load L in a directed fiber tree,
and thus that our algorithm is optimal in the class of greedy algorithms
which includes the algorithms presented in
Raghavan and Upfal (1991),
Mihail, Kaklamanis, and Rao (1995), Kaklamanis and Persiano (1996), and
Kumar and Schwabe (1997).
