TY - GEN
T1 - Strategies for hotlink assignments
AU - Bose, Prosenjit
AU - Czyzowicz, Jurek
AU - Gąsieniec, Leszek
AU - Kranakis, Evangelos
AU - Krizanc, Danny
AU - Pelc, Andrzej
AU - Martin, Miguel Vargas
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2000
Y1 - 2000
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84949790029&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84949790029&partnerID=8YFLogxK
U2 - 10.1007/3-540-40996-3_3
DO - 10.1007/3-540-40996-3_3
M3 - Conference contribution
AN - SCOPUS:84949790029
SN - 3540412557
SN - 9783540412557
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 23
EP - 34
BT - Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings
A2 - Lee, D.T.
A2 - Teng, Shang-Hua
A2 - Teng, Shang-Hua
PB - Springer Verlag
T2 - 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000
Y2 - 18 December 2000 through 20 December 2000
ER -