Approximate hotlink assignment Export

@article{kranakis_2004_hotlink, 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 = p 1 , p 2 ,…, p N on the N leaves of the given tree, i.e., p i is the weight on the i th leaf. The best known lower bound for this problem is H ( p )/log( d +1). We also show how to adapt our algorithm to complete trees of a given degree d and in this case we prove it is optimal, asymptotically in d .}, author = {Kranakis}, citeulike-article-id = {5046383}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.ipl.2004.01.012}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0020-0190(04)00039-0}, day = {16}, doi = {10.1016/j.ipl.2004.01.012}, issn = {00200190}, journal = {Information Processing Letters}, keywords = {clicks, graph}, month = {May}, number = {3}, pages = {121--128}, posted-at = {2009-07-03 14:29:27}, priority = {2}, title = {Approximate hotlink assignment}, url = {http://dx.doi.org/10.1016/j.ipl.2004.01.012}, volume = {90}, year = {2004} }

TY - JOUR ID - kranakis_2004_hotlink L3 - citeulike-article-id:5046383 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 = p 1 , p 2 ,…, p N on the N leaves of the given tree, i.e., p i is the weight on the i th leaf. The best known lower bound for this problem is H ( p )/log( d +1). We also show how to adapt our algorithm to complete trees of a given degree d and in this case we prove it is optimal, asymptotically in d . IS - 3 JF - Information Processing Letters SN - 00200190 EP - 128 TI - Approximate hotlink assignment VL - 90 SP - 121 KW - clicks KW - graph AU - Kranakis PY - 2004/05/16/ UR - http://dx.doi.org/10.1016/j.ipl.2004.01.012 ER -