网络1-重心反问题的计算复杂性研究

• 作者: 吴龙树 曹飞龙
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 1-重心 哈明距离 l1模 反问题 NP困难
• 年，卷（期）: 2011,（7）
• 所属期刊栏目: 开发研究与设计技术
• 页码范围: 274-275,278
• 分类号: TP301.6
• 字数: 3215字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2011.07.092

摘要

在网络中顶点的权值可以改变的情况下,对哈明距离下以及l1模下1-重心问题的反问题进行研究.通过将哈明距离下网络1-重心问题的反问题归约为0-1背包问题,证明即使是在链式网络中,在哈明距离下该问题仍是NP困难的,并给出l1模下在一般网络中求解1-重心反问题的多项式时间算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴龙树	中国计量学院理学院	9	17	3.0	3.0
2	曹飞龙	中国计量学院理学院	62	241	8.0	12.0