On the Complexity of Optimal Hotlink Assignment

On the Complexity of Optimal Hotlink Assignment

0.00 Avg rating0 Votes
Article ID: iaor2012421
Volume: 62
Issue: 3
Start Page Number: 982
End Page Number: 1005
Publication Date: Apr 2012
Journal: Algorithmica
Authors:
Keywords: networks, optimization, networks: path
Abstract:

The concept of hotlink assignment aims at reducing the navigation effort for users of a web directory or similar structure by inserting a limited number of additional hyperlinks called hotlinks. Given an access probability distribution of the leaves of the tree representing the web site, the goal of hotlink assignment algorithms is to minimize the expected path length between the root and the leaves. We prove that this optimization problem is NP‐hard, even if only one outgoing hotlink is allowed for each node. This answers a question that has been open since the first formulation of the problem in Bose et al. (2000) nine years ago. In this work we also investigate the model where hotlinks are only allowed to point at the leaves of the tree. We demonstrate that for this model optimal solutions can be computed in O(n 2) time. Our algorithm L‐OPT also operates in a more general setting, where the maximum number of outgoing hotlinks is specified individually for each node. The runtime is then O(n 3). Experimental evaluation shows that L‐OPT terminates within less than one second on problem instances having up to half a million nodes.

Reviews

Required fields are marked *. Your email address will not be published.