| TO IMPROVE THE COMMUNICATION DELAY BYUPGRADING NODES IN A CONTINUOUS VERSION |
| |
| 引用本文： | YANGXiaoguang. TO IMPROVE THE COMMUNICATION DELAY BYUPGRADING NODES IN A CONTINUOUS VERSION[J]. 系统科学与复杂性, 2005, 18(1): 67-73 |
| |
| 作者姓名： | YANGXiaoguang |
| |
| 作者单位： | InstituteofSystemsScience,AcademyofMathematicsandSystemsScience,ChineseAcademyofSciences,Beijing100080,China |
| |
| 基金项目： | This research is supported by National Key Researchand Development Programof China(No.2002CB312004)and the National Outstanding Youth Fund. |
| |
| 摘 要： | In this paper, we consider a network communication delay improvement prob-lem, which is to upgrade nodes in a network with minimum cost such that the communication delay between any two nodes of the network is below a pre-specific level. In the upgrading model, the improvement by upgrading one node is a continuous variable, and the cost incurred by such an upgrading is a linear function of the improvement. We show that achieving an approximation ratio β In(|V|) for the problem is NP-hard for some constant β＞0 even if the underlying network is a bipartite graph. But if the underlying network is restricted as a tree, we show that it can be solved in a strongly polynomial time.
|
| 关 键 词： | 信息处理 节点增强 信息迟滞 逼近比 不可逼近性 可解性 |
TO IMPROVE THE COMMUNICATION DELAY BY UPGRADING NODES IN A CONTINUOUS VERSION |
| |
| YANG Xiaoguang. TO IMPROVE THE COMMUNICATION DELAY BY UPGRADING NODES IN A CONTINUOUS VERSION[J]. Journal of Systems Science and Complexity, 2005, 18(1): 67-73 |
| |
| Authors: | YANG Xiaoguang |
| |
| Abstract: | |
| |
| Keywords: | Node upgrading delay approximating ratio inapproximability solvability. |
| 本文献已被 CNKI 维普 等数据库收录！ |
