交换机中周期流优化调度问题的复杂性

摘要：

研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性。依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题。并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法。

关键词： 交换机 周期流 优化调度

作者: 吴俊 李伟 李斌

作者单位: 扬州大学信息工程学院,扬州 225009 东南大学计算机科学与工程学院,南京 210096

会议类型: 国内会议

会议名称: 第十六届全国网络与数据通信学术会议(NDCC2008)

会议地点: 南京

会议语种:中文

页码: 8-11

在线出版日期: 2008-11-10（万方平台首次上网日期，不代表论文的发表时间）