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

被引：8

作者：

杨晓光

张建中

蔡茂诚

机构：

[1] 中国科学院数学与系统科学研究院系统科学研究所

[2] 香港城市大学数学系

[3] 中国科学院数学与系统科学研究院系统科学研究所北京

[4] 香港九龙

[5] 北京

来源：

关键词：

网络选址; 逆问题; 强NP困难;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

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

引用

页码：321 / 327

页数：7

共 6 条

[1]

Optimization Algorithms for Networks and Graphs. Evans J R and Minieka E. . 1992

[2]

The Steiner problem with edge lengths 1 and 2. Bern M and Plassmann P. Information ProcessingLetters . 1989

[3]

The complexity of theorem proving procedures. Cook S A. The Proceedings of the Third Annual ACM Symposium on the Theory of Computing . 1971

[4]

Graph Theory: An Algorithm ic Approach. Christofides N. . 1975

[5]

Combinatorial Optimization: Algorithms and Complexity. C.H.Papadimitriou,K.Steiglitz. . 1982

[6]

Reverse Center Location Problem. Zhang J,Yang X and Cai M. . 1999