求解Hamming距离下单位型单发点树型网络最短路改进问题的算法  

Algorithms for Solving the Unit Type Shortest Path Improvement Problems under Hamming Distance in Single-source Arborescence

作　　者：张斌武[1] 王勤[2] 

机构地区：[1]河海大学常州校区数理教学部,江苏常州213022 [2]中国计量学院理学院数学系,浙江杭州310018

出　　处：《河海大学常州分校学报》2007年第4期1-4,共4页Journal of Hohai University Changzhou

基　　金：国家自然科学基金资助项目(10601051)

摘　　要：给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质.解决了Hamming距离下逆问题(改进问题)中的部分问题,有助于设计出更多的求解Hamming距离下单位型树型网络最短路改进问题的算法.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.

关 键 词：HAMMING距离 最短路改进问题 NP-困难 多项式时间算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O221[自动化与计算机技术—计算机科学与技术]