 |
|
|||
| Authors: | Thomas Erlebach, Klaus Jansen |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | Maximizing the Number of Connections in Optical Tree Networks |
| Year: | 1998 |
| Pub-Key: | EJ98 |
| Book Titel: | Lecture Notes in Computer Science. Ninth Annual International Symposium on Algorithms and Computation (ISAAC 98) |
| Volume: | 1533 |
| Pages: | 179-188 |
| Keywords: | path coloring, edge-disjoint paths |
| Publisher: | Springer-Verlag |
| Abstract: | 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. |
| Location: | Taejon, Korea |
| Resources: | [BibTeX] |
