树状网络上的Web代理服务器最优放置问题  

Web proxy location problem in the tree networks

作　　者：陈光亭[1] 张固[1] 丁巍[1] 

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018

出　　处：《高校应用数学学报（A辑）》2004年第B12期510-514,共5页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(10371028);浙江省教育厅重点资助项目(20030622)

摘　　要：一般网络上Web代理服务器(Webproxy)最优放置问题是一个NP困难问题.此文讨论树状网络上的最优放置问题,改进了已有结果,得到了一个时间复杂度为O(nhk)的多项式时间算法,这里n为网络结点数,h为树的高度,而k为要放置的代理服务器个数.The Web proxy location problem in a general network is an NP-hard problem. The problem in tree topology networks is studied. The results in literature are improved,and an O（nhk） optimal algorithm is got,where n is the number of nodes in the tree,h is the height of the tree and k is the number of Web proxies to be placed in the net.

关 键 词：请求 代理服务器 树状网络 费用 

分 类 号：O157.5[理学—数学]