Hamming距离下的最短路逆问题

作     者：张斌武 王勤 ZHANG Bin-wu;WANG Qin

作者机构：河海大学数理部江苏常州213022 中国计量学院理学院浙江杭州310018 

基　　金：国家自然科学基金(10601051) 

出 版 物：《河海大学学报（自然科学版）》 (Journal of Hohai University(Natural Sciences))

年 卷 期：2008年第36卷第4期

页      码：571-574页

摘      要：针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.

主 题 词：Hamming距离 最短路 NP困难 多项式归约 3-SAT问题 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.3876/j.issn.1000-1980.2008.04.031

馆 藏 号：203125278...