Evaluation of hotlink assignment heuristics for improving web access

We study the optimal hotlink assignment problem. Consider a web site as a directed graph, where each page is represented by a node and each link is represented by an edge. The resulting graph is connected and may have cycles. It was previously proven that the hotlink assignment problem is NP-hard in its full generality. We describe a way of constructing a tree that maintains the original semantic relationship between the pages of a web site. We then proceed to describe three algorithms that improve access in web site trees. We simulate our algorithms in three different, but closely related, kinds of trees: power-law trees, realistic trees, and an actual tree. These algorithms are capable of obtaining considerable savings on the access cost of the web site.