【摘要】 本文考虑两个我们称之为逆网络选址的改进问题,它们是修改网络上各个边的长度,分别使得网络上某个给定的顶点到网络上所有点的最大距离以及该点到其它顶点的距离之和不大于预先给定的上界,并且所做的修改总量最小.我们将证明这两个逆网络选址问题都是强NP困难的.更多还原

【Abstract】 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.更多还原