Consider a DAG (directed acyclic graph) G = (V;E) re- presenting a collection V of web pages connected via links E. All web pages can be reached from a designated source page, represented by a source node s of G. Each web page carries a weight representative of the frequency with which it is visited. By adding hotlinks, at most one per page, we are interested in minimizing the expected number of steps needed to visit a selected set of web pages from the source page. For arbitrary DAGs we show that the problem is NP-complete. We also give algorithms for assigning hotlinks, as well as upper and lower bounds on the expected number of steps to reach the leaves from the source page s located at the root of a complete binary tree. Depending on the probability distribution (arbitrary, uniform, Zipf) the expected number of steps is at most c n, where c is a constant less than 1. For the geometric distribution we show how to obtain a constant average number of steps.

Additional Metadata
Citation
Bose, P, Czyzowicz, J. (Jurek), G─ůsieniec, L. (Leszek), Kranakis, E, Krizanc, D. (Danny), Pelc, A. (Andrzej), & Martin, M.V. (Miguel Vargas). (2000). Strategies for hotlink assignments.