### 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 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### 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

}

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

**Approximate hotlink assignment.** / Kranakis, Evangelos; Krizanc, Danny; Shende, Sunil.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximate hotlink assignment

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Shende, Sunil

PY - 2001/12/1

Y1 - 2001/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70350640675&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350640675&partnerID=8YFLogxK

U2 - 10.1007/3-540-45678-3_64

DO - 10.1007/3-540-45678-3_64

M3 - Conference contribution

AN - SCOPUS:70350640675

SN - 3540429859

SN - 9783540429852

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

SP - 756

EP - 767

BT - Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings

ER -