Resource allocation problems in multifiber WDM tree networks. (English) Zbl 1255.90028
Bodlaender, Hans L. (ed.), Graph-theoretic concepts in computer science. 29th international workshop, WG 2003, Elspeet, The Netherlands, June 19–21, 2003. Revised papers. Berlin: Springer (ISBN 3-540-20452-0/pbk). Lect. Notes Comput. Sci. 2880, 218-229 (2003).
Summary: All-optical networks with multiple fibers lead to several interesting optimization problems. In this paper, we consider the problem of minimizing the total number of fibers necessary to establish a given set of requests with a bounded number \(w\) of wavelengths, and the problem of maximizing the number of accepted requests for given fibers and bounded number \(w\) of wavelengths. We study both problems in undirected tree networks \(T=(V,E)\) and present approximation algorithms with ratio \(1+4| E|\log | V|/\mathrm{OPT}\) and 4 for the former and ratio 2.542 for the latter. Our results can be adapted to directed trees as well.
For the entire collection see [Zbl 1029.00043].
For the entire collection see [Zbl 1029.00043].
MSC:
| 90B18 | Communication networks in operations research |
| 68W25 | Approximation algorithms |
| 90C35 | Programming involving graphs or networks |
