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

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

给出了求解两类特殊的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.