摘要： 在网络中顶点的权值可以改变的情况下，对哈明距离下以及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
中图分类号:
吴龙树, 曹飞龙. 网络1-重心反问题的计算复杂性研究[J]. 计算机工程, 2011, 37(7): 274-275,278.
TUN Long-Shu, CAO Fei-Long. Research on Computational Complexity of Reverse Network 1-median Problem[J]. Computer Engineering, 2011, 37(7): 274-275,278.