网络最短路的提速问题

摘要：

网络最短路提速问题起源于交通运输、计算机信息传输等领域,具有重要的理论和实际应用意义.对一般网络来说,该问题是NP-完全的.对(0,1)-提速问题的指定路线的提速问题两种情况分别进行了研究,证明了(0,1)-提速问题是NP-完全的、一般网络在指定路线情形下的提速问题是多项式可解的,给出了单源多汇网络G中提速问题的O(nm log n)算法.

关键词：网络最短路、线性规划、网络提速、算法

所属期刊栏目：30

分类号：O157.6;O22(代数、数论、组合理论)

资助基金：国家自然科学基金项目11101383:河南省科学发展计划基础与前沿技术研究项目112300410047;河南省高校科技创新人才支持计划2010HASTIT043

在线出版日期：2012-07-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：302-307