Bibliographic Details
| Title: |
Satisfying a maximum number of pre-routed requests in all-optical rings |
| Authors: |
Nomikos, Christos1 cnomikos@cs.uoi.gr, Pagourtzis, Aris2,3 pagour@inf.ethz.ch, Zachos, Stathis3,4 zachos@cs.ntua.gr |
| Source: |
Computer Networks. May2003, Vol. 42 Issue 1, p55. 9p. |
| Subjects: |
Telecommunication, Algorithms |
| Abstract: |
We address the problem of maximizing the number of satisfied requests in all-optical networks that use wavelength division multiplexing. We consider the case where requests are pre-routed and formulate it as the maximum path coloring problem. We study the problem for rings and present a (2/3)-approximation algorithm. Along the way we develop a fast matching technique for a special class of bipartite graphs. By using this technique we achieve an O(n+mlogL) time complexity for our approximation algorithm, where n is the number of nodes, m is the number of requests and L is the maximum load of requests on a single link. [Copyright &y& Elsevier] |
|
Copyright of Computer Networks is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
