作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (7): 274-275,278. doi: 10.3969/j.issn.1000-3428.2011.07.092

• 开发研究与设计技术 • 上一篇    下一篇

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

吴龙树,曹飞龙   

  1. (中国计量学院理学院,杭州 310018)
  • 出版日期:2011-04-05 发布日期:2011-03-31
  • 作者简介:吴龙树(1975-),男,副教授、硕士,主研方向:网络近似算法设计;曹飞龙,教授、博士
  • 基金资助:
    国家自然科学基金重大计划资助项目(90818020);国家自然科学基金资助项目(10601051);浙江省自然科学基金资助项目(Y6090472);浙江省教育厅科研基金资助项目(Y201018835)

Research on Computational Complexity of Reverse Network 1-median Problem

WU Long-shu, CAO Fei-long   

  1. (College of Science, China Jiliang University, Hangzhou 310018, China)
  • Online:2011-04-05 Published:2011-03-31

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

关键词: 1-重心, 哈明距离, l1模, 反问题, NP困难

Abstract: This paper researches the reverse 1-median problem under the hamming distance and l1-norm in condition that the weights of vertices in a network can be changed. Under the hamming distance, by transforming this problem to a 0-1 knapsack problem, it proves that even in chain network, this problem is NP-hard. Under l1-norm, it presents a polynomial time algorithm to solve the problem in general network.

Key words: 1-median, Hamming distance, l1-norm, reverse problem, NP-hard

中图分类号: