The web proxy location problem in general tree of rings networks

Guangting Chen*, Gu Zhang, Rainer Ernst Burkard

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)327-336
JournalJournal of Combinatorial Optimization
Publication statusPublished - 2006

Cite this