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

Research on Computational Complexity of Reverse Network 1-median Problem

作　　者：吴龙树[1] 曹飞龙[1] 

机构地区：[1]中国计量学院理学院,杭州310018

出　　处：《计算机工程》2011年第7期274-275,278,共3页Computer Engineering

基　　金：国家自然科学基金重大计划资助项目(90818020);国家自然科学基金资助项目(10601051);浙江省自然科学基金资助项目(Y6090472);浙江省教育厅科研基金资助项目(Y201018835)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]