两个逆网络选址问题的计算复杂性  

COMPLEXITY OF TWO REVERSE NETWORK LOCATION PROBLEMS

作　　者：杨晓光[1] 张建中[2] 蔡茂诚[1] 

机构地区：[1]中国科学院数学与系统科学研究院系统科学研究所,北京100080 [2]香港城市大学数学系

出　　处：《系统科学与数学》2002年第3期321-327,共7页Journal of Systems Science and Mathematical Sciences

基　　金：香港高校基金会(CERG CITYU-9040651);国家自然科学基金(70071045;19971001)资助课题.

摘　　要：本文考虑两个我们称之为逆网络选址的改进问题,它们是修改网络上各个边的长度,分别使得网络上某个给定的顶点到网络上所有点的最大距离以及该点到其它顶点的距离之和不大于预先给定的上界,并且所做的修改总量最小.我们将证明这两个逆网络选址问题都是强NP困难的.The paper discusses two network improvement problems which we call the reverse network location problems. They are to change the lengths of the edges of the network to ensure that the maximal distance from a given vertex to other vertices is not bigger than a given upper bound, or the sum of distances from a given vertex to other vertices is not bigger than a given upper bound; and the total changes are minimum. We show that both the reverse problems are strongly NP-hard.

关 键 词：计算复杂性 网络选址 逆问题 强NP困难 中心选址问题 连通图 

分 类 号：O157.5[理学—数学] O224[理学—基础数学]