The web proxy location problem in general tree of rings networks |
| |
| Authors: | Guangting Chen Gu Zhang Rainer E Burkard |
| |
| Institution: | 1. The Institute of Operational Research and Cybernetics, Hangzhou Dianzi University, Hangzhou, 310018, P.R. China
2. Technische Universit?t Graz, Institut für Mathematik, Steyrergasse 30, A-8010, Graz, Austria
|
| |
| Abstract: | The Web proxy location problem in general networks is an NP-hard problem. In this paper, we study the problem in networks showing a general tree of rings topology. We improve the results of the tree case in literature and get an exact algorithm with time complexity O(nhk), where n is the number of nodes in the tree, h is the height of the tree (the server is in the root of the tree), and k is the number of web proxies to be placed in the net. For the case of networks with a general tree of rings topology we present an exact algorithm with O(kn
2) time complexity.This research has been supported by NSF of China (No. 10371028) and the Educational Department grant of Zhejiang Province (No. 20030622). |
| |
| Keywords: | Location problem Tree General tree of rings Proxy Placement |
| 本文献已被 SpringerLink 等数据库收录！ |
|
