Maximizing the Number of Connections in Optical Tree Networks
Proceedings of the Ninth International Symposium on
Algorithms and Computation (ISAAC'98),
LNCS 1533, Springer Verlag, 1998, pp. 179-188.
In optical networks with wavelength division multiplexing (WDM),
multiple connections can share a link if they are transmitted on
different wavelengths. We study the problem of satisfying a maximum
number of connection requests in a directed tree network if only a
limited number W of wavelengths are available. In optical networks
without wavelength converters this is the maximum path coloring
(MaxPC) problem, in networks with full wavelength conversion this is the
maximum path packing (MaxPP) problem. MaxPC and MaxPP are shown
to be polynomial-time solvable to optimality if the tree has
height one or if both W and the degree of the tree are bounded by a
constant. If either W or the degree of the tree is not bounded by a
constant, MaxPC and MaxPP are proved NP-hard. Polynomial-time
approximation algorithms with performance ratio 5/3+epsilon for
arbitrarily small epsilon are presented for the case W=1, in
which MaxPC and MaxPP are equivalent. For arbitrary W, a
2-approximation for MaxPP in arbitrary trees, a 1.58-approximation
for MaxPC in trees of bounded degree, and a 2.22-approximation for
MaxPC in arbitrary trees are obtained.
