哈明距离下的最短路反问题

• 作者: 陈志民
• 来源期刊: 长春师范学院学报：自然科学版
• 学科: 数学
• 关键词: 最短路 反问题 计算复杂性
• 年，卷（期）: 2007,（2）
• 页码范围: 24-26
• 页数: 3页
• 分类号: O224

摘要

反优化问题是指修改给定的参数，使得优化问题的最优解的目标函数值满足一定的约束。本文中我们考虑的是哈明距离下的最短路反问题：通过修改给定网络上弧的长度，使得修改后网络中指定点之间的最短路长度不超过给定的常数，而其中修改费用是用哈明距离来衡量的，我们证明了哈明距离下的最短路反问题是强NP-完全的。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈志民		11	13	2.0	3.0