The web proxy location problem in general tree of rings networks
Source: Journal of Combinatorial Optimization, Volume 12, Number 4, December 2006 , pp. 327-336(10)
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.
Document Type: Research article
Publication date: 2006-12-01