### Abstract

Consider a directed rooted tree T = (V,E) of maximal degree d representing a collection V of web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each leaf web page carries a weight representative of the frequency with which it is visited. By adding hotlinks, shortcuts from a node to one of its descendents, we are interested in minimizing the expected number of steps needed to visit the leaf pages from the home page. We give an O(N ^{2}) time algorithm for assigning hotlinks so that the expected number of steps to reach the leaves from the root of the tree is at most H(p)/ log(d+1)-(d/(d+1)) log d + d+1/d, where H(p) is the entropy of the probability (frequency) distribution p =< p1,p2, pN > on the N leaves of the given tree, i.e., pi is the weight on the ith leaf. The best known lower bound for this problem is H(p)/ log(d+1). Thus our algorithm approximates the optimal hotlink assignment to within a constant for any fixed d.

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings |

Pages | 756-767 |

Number of pages | 12 |

DOIs | |

State | Published - Dec 1 2001 |

Event | 12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, New Zealand Duration: Dec 19 2001 → Dec 21 2001 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2223 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 12th International Symposium on Algorithms and Computation, ISAAC 2001 |
---|---|

Country | New Zealand |

City | Christchurch |

Period | 12/19/01 → 12/21/01 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Approximate hotlink assignment'. Together they form a unique fingerprint.

## Cite this

*Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings*(pp. 756-767). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2223 LNCS). https://doi.org/10.1007/3-540-45678-3_64