TO IMPROVE THE COMMUNICATION DELAY BY UPGRADING NODES IN A CONTINUOUS VERSION  

作　　者：YANGXiaoguang 

机构地区：[1]InstituteofSystemsScience,AcademyofMathematicsandSystemsScience,ChineseAcademyofSciences,Beijing100080,China

出　　处：《Journal of Systems Science & Complexity》2005年第1期67-73,共7页系统科学与复杂性学报（英文版）

基　　金：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 problem,which is to upgrade nodes in a network with minimum cost such that the communication delay betweenany two nodes of the network is below a pre-specific level. In the upgrading model, the improvementby upgrading one node is a continuous variable, and the cost incurred by such an upgrading is alinear function of the improvement. We show that achieving an approximation ratio βln(|V|) for theproblem is NP-hard for some constant β > 0 even if the underlying network is a bipartite graph. Butif the underlying network is restricted as a tree, we show that it can be solved in a stronglypolynomial time.

关 键 词：node upgrading DELAY approximating ratio INAPPROXIMABILITY SOLVABILITY 

分 类 号：TN911.7[电子电信—通信与信息系统]