COMPLEXITY OF TWO REVERSE NETWORK LOCATION PROBLEMS
两个逆网络选址问题的计算复杂性

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.