Advertisement
Published in:
2006 | OriginalPaper | Chapter
Approximating the Traffic Grooming Problem in Tree and Star Networks
Authors : Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, Shmuel Zaks
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the problem of grooming paths in all-optical networks with tree topology so as to minimize the switching cost, measured by the total number of used ADMs. We first present efficient approximation algorithms with approximation factor of 2 ln (
δ
g
) +
o
(ln (
δ
g
)) for any fixed node degree bound
δ
and grooming factor
g
, and 2ln
g
+
o
( ln
g
) in unbounded degree directed trees, respectively. In the attempt of extending our results to general undirected trees we completely characterize the complexity of the problem in star networks by providing polynomial time optimal algorithms for
g
≤2 and proving the intractability of the problem for any fixed
g
>2. While for general topologies the problem was known to be NP-hard
g
not constant, the complexity for fixed values of
g
was still an open question.