 |
|
|||
| Authors: | Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, Pino Persiano |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | An Optimal Greedy Algorithm for Wavelength Allocation in Directed Tree Networks |
| Year: | 1998 |
| Pub-Key: | EJKP98 |
| Book Titel: | DIMACS Series in Discrete Mathematics and Theoretical Computer Science. DIMACS Workshop on Network Design: Connectivity and Facilities Location |
| Volume: | 40 |
| Pages: | 117-129 |
| Keywords: | path coloring |
| Publisher: | American Mathematical Society |
| Abstract: | The problem of allocating wavelengths in optical networks with directed tree topology has recently received a substantial amount of attention. Wavelengths must be assigned to connection requests which are represented as directed paths, and it is required that paths receive different wavelengths if they share a directed link. The goal is to minimize the number of different wavelengths used. The best previously known approximation algorithm for this NP-hard problem routes any set of paths with 7L/4 wavelengths, where L is the maximum load on a directed link. We give an improved algorithm that uses at most 5L/3 wavelengths. This is provably the best ratio that can be achieved by any local greedy algorithm for this problem. |
| Location: | DIMACS, New Brunswick |
| Resources: | [BibTeX] |
