Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (19): 39-41.
• 研究、探讨 • Previous Articles Next Articles
BAI Yanqin,WANG Qin,WU Longshu
Received:
Revised:
Online:
Published:
白艳琴,王 勤,吴龙树
Abstract: 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.
Key words: 1-median, Hamming distance, reverse problem, dynamic programming, NP-hard
摘要: 主要讨论哈明距离下网络中的1-重心问题的反问题。1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界。证明了在哈明距离下该问题是NP困难的。并运用动态规划的思想,在考虑改变顶点的权的情况下,对一般网络进行了求解。
关键词: 1-重心, 哈明距离, 反问题, 动态规划, NP困难
BAI Yanqin,WANG Qin,WU Longshu. Reverse 1-median problem under Hamming distance[J]. Computer Engineering and Applications, 2011, 47(19): 39-41.
白艳琴,王 勤,吴龙树. 哈明距离下1-重心问题的反问题[J]. 计算机工程与应用, 2011, 47(19): 39-41.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/
http://cea.ceaj.org/EN/Y2011/V47/I19/39