摘要
主要讨论哈明距离下网络中的1-重心问题的反问题。1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界。证明了在哈明距离下该问题是NP困难的。并运用动态规划的思想,在考虑改变顶点的权的情况下,对一般网络进行了求解。
This paper mainly discusses the reverse 1-median problem under the Hamming distance.The reverse 1-median problem is to reduce the overall sum of the weighted distances from the vertices to a given vertex by changing the parameters in a network such that it can satisfy a given budget,and the cost for changing the parameters is as small as possible. Under the hamming distance,it shows that this problem is NP-hard.By using dynamic programming method,this problem is solved in a general network by changing the weights of vertices.
出处
《计算机工程与应用》
CSCD
北大核心
2011年第19期39-41,共3页
Computer Engineering and Applications
基金
国家自然科学基金No.10601051
浙江省自然科学基金(No.Y6090472)
浙江省教育厅科研项目(No.Y201018835)~~
关键词
1-重心
哈明距离
反问题
动态规划
NP困难
1-median
Hamming distance
reverse problem
dynamic programming
NP-hard