针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.
张斌武,王勤. Hamming距离下的最短路逆问题[J].河海大学学报(自然科学版),2008,(4):571-574.(.[J]. Journal of Hohai University (Natural Sciences),2008,(4):571-574.(in Chinese))