首页> 中文期刊>河海大学学报（自然科学版） >Hamming距离下的最短路逆问题

Hamming距离下的最短路逆问题

开具论文收录证明 >>

期刊封面封底目录下载 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《河海大学学报（自然科学版）》|2008年第4期|571-574|共4页
作者
张斌武; 王勤;
展开▼
作者单位

河海大学数理部,江苏,常州213022;

中国计量学院理学院,浙江,杭州310018;

展开▼
原文格式 PDF
正文语种 chi
中图分类规划论（数学规划）;
关键词
Hamming距离; 最短路; NP困难; 多项式归约; 3-SAT问题;

相似文献

中文文献
外文文献
专利

1. 求解Hamming距离下的最短路改进问题的一个近似算法 [J] . 张斌武 ,王勤 ,余维燕 . 兰州理工大学学报 . 2008,第004期
2. 求解单位L∞范数下带值约束的最短路逆问题的算法 [J] . 于成成 ,周泽聿 ,张斌武 . 计算机与数字工程 . 2020,第009期
3. Hamming距离下树型网络的最短路改进问题 [J] . 张斌武 ,王勤 . 兰州理工大学学报 . 2008,第002期
4. 求解Hamming距离下单位型单发点树型网络最短路改进问题的算法 [J] . 张斌武 ,王勤 . 河海大学常州分校学报 . 2007,第004期
5. Hamming距离下瓶颈约束最小支撑树反问题 [J] . 刘洋 ,唐恒永 . 牡丹江师范学院学报（自然科学版） . 2009,第001期
6. 赋权l<,∞>模意义下的约束瓶颈支撑树问题的逆问题 [C] . 关秀翠 ,张建中 . 中国运筹学会第七届学术交流会 . 2004
7. Hamming距离下约束最小支撑树的反问题 [A] . 焦丽 . 2009

获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

客服微信
服务号