TY - JOUR
T1 - Maximizing profits of routing in WDM networks
AU - Li, Jianping
AU - Li, Kang
AU - Wang, Lusheng
AU - Zhao, Hao
PY - 2005/9
Y1 - 2005/9
N2 - Let G = (V, E) be a ring (or chain) network representing an optical wavelength division multiplexing (WDM) network with k channels, where each edge ej has an integer capacity cj. A request s i,t i is a pair of two nodes in G. Given m requests si,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 ej 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. © 2005 Springer Science + Business Media, Inc.
AB - Let G = (V, E) be a ring (or chain) network representing an optical wavelength division multiplexing (WDM) network with k channels, where each edge ej has an integer capacity cj. A request s i,t i is a pair of two nodes in G. Given m requests si,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 ej 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. © 2005 Springer Science + Business Media, Inc.
KW - Approximation algorithm
KW - Minimum-cost flow
KW - Path coloring
KW - Routing
UR - http://www.scopus.com/inward/record.url?scp=24144487721&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-24144487721&origin=recordpage
U2 - 10.1007/s10878-005-2263-0
DO - 10.1007/s10878-005-2263-0
M3 - 21_Publication in refereed journal
VL - 10
SP - 99
EP - 111
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 2
ER -