The web proxy location problem in general tree of rings networks

Authors: Chen, Guangting¹; Zhang, Gu²; Burkard, Rainer³

Source: Journal of Combinatorial Optimization, Volume 12, Number 4, December 2006 , pp. 327-336(10)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

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 ²) time complexity.

Keywords: Location problem; Tree; General tree of rings; Proxy; Placement

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10878-006-9002-z

Affiliations: 1: Email: gtchen@hdu.edu.cn 2: Email: zhanggu@sci.hziee.edu.cn 3: Email: burkard@tugraz.at

Publication date: 2006-12-01