| 网络最短路的提速问题 |
| |
| 引用本文： | 张振坤,叶希琼. 网络最短路的提速问题[J]. 河南科学, 2012, 0(3): 302-307 |
| |
| 作者姓名： | 张振坤 叶希琼 |
| |
| 作者单位： | [1]黄淮学院数学系,河南驻马店463000 [2]郑州电子信息工程学校公共教学部,郑州450007 |
| |
| 基金项目： | 国家自然科学基金项目（11101383）;河南省科学发展计划基础与前沿技术研究项目（112300410047）;河南省高校科技创新人才支持计划（2010HASTIT043） |
| |
| 摘 要： | 网络最短路提速问题起源于交通运输、计算机信息传输等领域,具有重要的理论和实际应用意义.对一般网络来说,该问题是NP-完全的.对(0,1)-提速问题的指定路线的提速问题两种情况分别进行了研究,证明了(0,1)-提速问题是NP-完全的、一般网络在指定路线情形下的提速问题是多项式可解的,给出了单源多汇网络G中提速问题的O(nm log n)算法.
|
| 关 键 词： | 网络最短路 线性规划 网络提速 算法 |
The Routing Speed-up Problem of the Shortest Path for Networks |
| |
| Zhang Zhenkun,Ye Xiqiong. The Routing Speed-up Problem of the Shortest Path for Networks[J]. Henan Science, 2012, 0(3): 302-307 |
| |
| Authors: | Zhang Zhenkun Ye Xiqiong |
| |
| Affiliation: | 2 (1. Department of Mathematics, Huanghuai University, Zhumadian 463000, Henan China; 2. Communal Teaching Department, Zhengzhou Electronic Information Engineering College, Zhengzhou 450007, China) |
| |
| Abstract: | The routing speed-up problem of the shortest path for networks, stemming from the transportation and other areas, has important theoretical and application meanings. For general networks, the problem is NP-eomplete. In this paper, two special cases of this problem, which are （0, 1）-routing speed-up problem and specified routing speed-up problem respectively, are investigated. The （0, 1）-routing speed-up problem is NP-complete, the specified routing speed-up problem for general networks is solvable in polynomial time, and an O （nm log n） algorithm to solve the routing speed-up problem is given in network G with one source and k （k≥2） terminals. |
| |
| Keywords: | shortest path of network linear programming routing speed-up problem algorithm |
| 本文献已被 维普 等数据库收录！ |
|
