|
|||||
|
|
| 求解Hamming距离下单位型单发点树型网络最短路改进问题的算法 | |
| 引用本文： | 张斌武,王勤. 求解Hamming距离下单位型单发点树型网络最短路改进问题的算法[J]. 河海大学常州分校学报, 2007, 21(4): 1-4 |
| 作者姓名： | 张斌武 王勤 |
| 作者单位： | 1. 河海大学,常州校区数理教学部,江苏,常州,213022 2. 中国计量学院,理学院数学系,浙江,杭州,310018 |
| 摘 要： | 给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质.解决了Hamming距离下逆问题(改进问题)中的部分问题,有助于设计出更多的求解Hamming距离下单位型树型网络最短路改进问题的算法. |
| 关 键 词： | Hamming距离 最短路改进问题 NP-困难 多项式时间算法 |
| 文章编号： | 1009-1130(2007)04-0001-04 |
| 修稿时间： | 2007-11-14 |
Algorithms for Solving the Unit Type Shortest Path Improvement Problems under Hamming Distance in Single-source Arborescence |
|
| ZHANG Bin-wu,WANG Qin. Algorithms for Solving the Unit Type Shortest Path Improvement Problems under Hamming Distance in Single-source Arborescence[J]. Journal of Hohai University Changzhou, 2007, 21(4): 1-4 | |
| Authors: | ZHANG Bin-wu WANG Qin |
| Abstract: | In this paper,we gave two polynomial-time algorithms for solving two special unit type shortest path improvement problems under Hamming distance in single-source arborescence,and we studied some properties of the general problem.This paper answered some open problems given in the review paper on the inverse(improvement)problem under Hamming distance.We hope this paper could be useful for designing some more algorithms for the unit type shortest path improvement problems under Hamming distance in arborescence. |
| Keywords: | Hamming distance the shortest path improvement problem NP-hard polynomial-time algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |