多纤波分复用链网与环网中的利润极大化问题

多纤波分复用链网与环网中的利润极大化问题

李曙光^1,2,杨振光³,何志红¹

1. 山东大学数学与系统科学学院，山东济南250100；2. 烟台大学数学与信息科学系，山东烟台264005；3. 鲁东大学数学与信息学院，山东烟台264025

收稿日期:2005-11-25 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 李曙光

Maximizing profits in multifiber WDM chain and ring networks

LI Shu-guang^1,2,YANG Zhen-guang³,HE Zhi-hong¹

1. School of Math. and System Sci., Shandong Univ., Jinan 250100, Shandong, China; 2. Department of Math. and Info. Sci., Yantai Univ., Yantai 264005, Shandong, China;3. School of Math. and Info., Ludong Univ., Yantai 264025, Shandong, China

Received:2005-11-25 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: LI Shu-guang

摘要/Abstract

摘要： 考虑多纤波分复用链网与环网中的利润极大化问题, 分别给出了多项式时间精确算法和2近似算法. 对于环上各边光纤数目相同的均匀模式, 给出了1.582近似算法. 这些结果也适用于有向链网与环网.

关键词: 近似算法, 多纤光网络, 路染色 , 路由, 波分复用

Abstract: ]Abstract: The problem of the total maximizing profits of accepted requests in multifiber WDM chain and ring networks is considered. A polynomial time exact algorithm to solve the problem for chains and a 2approximation algorithm for rings are presented. The uniform variant in rings where all edges have the same number of fibers is also considered and a 1.582approximation algorithm is presented. These results can also be adapted to the directed chains and rings.

Key words: path coloring , routing, WDM, multifiber optical networks, approximation algorithms

李曙光,杨振光,何志红 . 多纤波分复用链网与环网中的利润极大化问题[J]. J4, 2006, 41(5): 7-11 .

LI Shu-guang,YANG Zhen-guang,HE Zhi-hong . Maximizing profits in multifiber WDM chain and ring networks[J]. J4, 2006, 41(5): 7-11 .

参考文献

相关文章 15

[1]	仲诚诚,周恒,张梓童,张春雷. LAC-UNet: 基于胶囊表达局部-整体特征关系的语义分割模型[J]. 《山东大学学报(理学版)》, 2023, 58(11): 116-126.
[2]	邱修峰1,2,刘建伟1,伍前红1,刘建华1. 多路径域间路由决策检测协议[J]. J4, 2013, 48(7): 39-45.
[3]	郭晓东，焦亮，仇一泓，葛连升. 基于Click和NS2的多路径域间路由仿真器的设计与实现[J]. J4, 2013, 48(11): 36-43.
[4]	蔡裕华,魏凤英*. 度量空间的概率近似算法[J]. J4, 2013, 48(09): 51-55.
[5]	蒋华,李明珍,王鑫. 一种基于概率包标记的PPM算法改进方案[J]. J4, 2011, 46(9): 85-88.
[6]	葛连升1,周加强2,秦丰林1. 基于交叉熵的多约束QoS组播路由蚂蚁算法[J]. J4, 2010, 45(5): 35-41.
[7]	葛连升江林秦丰林. QoS组播路由算法研究综述[J]. J4, 2010, 45(1): 55-65.
[8]	杨朝霞 . 超图嵌入带权重圈的一个2-近似算法[J]. J4, 2008, 43(8): 11-13 .
[9]	石钊,葛连升,* . 一种解多QoS约束组播问题的改进蚁群算法[J]. J4, 2007, 42(9): 41-45 .
[10]	杨振光,李曙光,王秀红 . 工件尺寸不同的并行机批调度问题[J]. J4, 2007, 42(4): 63-66 .
[11]	戴珍香,李曙光,亓兴勤 . 波分复用星形单跳网中3信道的传输调度问题[J]. J4, 2007, 42(2): 46-50 .
[12]	亓兴勤,曹静,张晨 . 环型二元序列的赋权对换排序问题[J]. J4, 2007, 42(12): 46-48 .
[13]	李曙光,白淑岩,何志红,亓兴勤 . 圈中t-区间的k-染色问题[J]. J4, 2006, 41(6): 40-42 .
[14]	李曙光,亓兴勤,何志红 . 环网络中的呼叫接纳控制[J]. J4, 2006, 41(4): 15-19 .
[15]	王继强, . 一类median问题的近似算法研究[J]. J4, 2006, 41(4): 1-03 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed