| 两个逆网络选址问题的计算复杂性 |
| |
| 引用本文： | 杨晓光,张建中,蔡茂诚. 两个逆网络选址问题的计算复杂性[J]. 系统科学与数学, 2002, 22(3): 321-327 |
| |
| 作者姓名： | 杨晓光 张建中 蔡茂诚 |
| |
| 作者单位： | 1. 中国科学院数学与系统科学研究院系统科学研究所,北京,100080
2. 香港城市大学数学系,香港,九龙 |
| |
| 基金项目： | 香港高校基金会（CERG CITYU-9040651），国家自然科学基金（70071045，19971001）资助课题. |
| |
| 摘 要： | 本文考虑两个我们称之为逆网络选址的改进问题,它们是修改网络上各个边的长度,分别使得网络上某个给定的顶点到网络上所有点的最大距离以及该点到其它顶点的距离之和不大于预先给定的上界,并且所做的修改总量最小.我们将证明这两个逆网络选址问题都是强NP困难的.
|
| 关 键 词： | 网络选址 逆问题 强NP困难 |
COMPLEXITY OF TWO REVERSE NETWORK LOCATION PROBLEMS |
| |
| Yang Xiaoguang. COMPLEXITY OF TWO REVERSE NETWORK LOCATION PROBLEMS[J]. Journal of Systems Science and Mathematical Sciences, 2002, 22(3): 321-327 |
| |
| Authors: | Yang Xiaoguang |
| |
| Affiliation: | (1)Institute of Systems Sci.,Academy of Math.and Systems Sci.,Chinese Academy of Sciences, Beijing 100080,P.R.China;(2)Department of Math.,City Univ.of Hong Kong ,Hong Kong;(3)Inst.of Systems Sic.,Academy of Math.and Systems Sic.,Chin.Academy of Sci.,Beijing 100080,P.R.China |
| |
| 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. |
| |
| Keywords: | Network location reverse problem strongly NP-hard. |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
|
点击此处可从《系统科学与数学》下载全文 |
|
