toimprovethecommunicationdelaybyupgradingnodesinacontinuousversion

CSpace > 系统科学研究所

	toimprovethecommunicationdelaybyupgradingnodesinacontinuousversion
	Yang Xiaoguang
	2005-01-01
发表期刊	journalofsystemsscienceandcomplexity
ISSN	1009-6124
卷号	018 期号:001 页码:67
摘要	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.
语种	英语
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/46977
专题	系统科学研究所
作者单位	中国科学院数学与系统科学研究院
推荐引用方式 GB/T 7714	Yang Xiaoguang. toimprovethecommunicationdelaybyupgradingnodesinacontinuousversion[J]. journalofsystemsscienceandcomplexity,2005,018(001):67.
APA	Yang Xiaoguang.(2005).toimprovethecommunicationdelaybyupgradingnodesinacontinuousversion.journalofsystemsscienceandcomplexity,018(001),67.
MLA	Yang Xiaoguang."toimprovethecommunicationdelaybyupgradingnodesinacontinuousversion".journalofsystemsscienceandcomplexity 018.001(2005):67.