Maximizing Profits of Routing in WDM Networks

Jianping Li (), Kang Li (), Lusheng Wang () and Hao Zhao ()
Additional contact information
Jianping Li: Yunnan University
Kang Li: Shandong University
Lusheng Wang: City University of Hong Kong
Hao Zhao: City University of Hong Kong

Journal of Combinatorial Optimization, 2005, vol. 10, issue 2, No 1, 99-111

Abstract: Abstract Let G = (V, E) be a ring (or chain) network representing an optical wavelength division multiplexing (WDM) network with k channels, where each edge e j has an integer capacity c j . A request s i ,t i is a pair of two nodes in G. Given m requests s i ,t i , i = 1, 2, ..., m, each with a profit value p i , we would like to design/route a k-colorable set of paths for some (may not be all) of the m requests such that each edge e j in G is used at most c j times and the total profit of the set of designed paths is maximized. Here two paths cannot have the same color (channel) if they share some common edge(s). This problem arises in optical communication networks. In this paper, we present a polynomial-time algorithm to solve the problem when G is a chain. When G is a ring, however, the optimization problem is NP-hard (Wan and Liu, 1998), we present a 2-approximation algorithm based on our solution to the chain network. Similarly, some results in a bidirected chain and a bidirected ring are obtained.

Keywords: minimum-cost flow; routing; path coloring; approximation algorithm (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-2263-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:10:y:2005:i:2:d:10.1007_s10878-005-2263-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-005-2263-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().