Strategies for hotlink assignments

Prosenjit Bose; Jurek Czyzowicz; Leszek Gąsieniec; Evangelos Kranakis; Danny Krizanc; Andrzej Pelc; Miguel Vargas Martin

doi:10.1007/3-540-40996-3_3

Strategies for hotlink assignments

Prosenjit Bose, Jurek Czyzowicz, Leszek Gąsieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin

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

37 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings
Editors	D.T. Lee, Shang-Hua Teng, Shang-Hua Teng
Publisher	Springer Verlag
Pages	23-34
Number of pages	12
ISBN (Print)	3540412557, 9783540412557
DOIs	https://doi.org/10.1007/3-540-40996-3_3
State	Published - 2000
Externally published	Yes
Event	11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 - Taipei, Taiwan, Province of China Duration: Dec 18 2000 → Dec 20 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1969
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th Annual International Symposium on Algorithms and Computation, ISAAC 2000
Country/Territory	Taiwan, Province of China
City	Taipei
Period	12/18/00 → 12/20/00

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-40996-3_3

Cite this

Bose, P., Czyzowicz, J., Gąsieniec, L., Kranakis, E., Krizanc, D., Pelc, A., & Martin, M. V. (2000). Strategies for hotlink assignments. In D. T. Lee, S.-H. Teng, & S.-H. Teng (Eds.), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings (pp. 23-34). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969). Springer Verlag. https://doi.org/10.1007/3-540-40996-3_3

Strategies for hotlink assignments. / Bose, Prosenjit; Czyzowicz, Jurek; Gąsieniec, Leszek et al.
Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. ed. / D.T. Lee; Shang-Hua Teng; Shang-Hua Teng. Springer Verlag, 2000. p. 23-34 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969).

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

Bose, P, Czyzowicz, J, Gąsieniec, L, Kranakis, E, Krizanc, D, Pelc, A & Martin, MV 2000, Strategies for hotlink assignments. in DT Lee, S-H Teng & S-H Teng (eds), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1969, Springer Verlag, pp. 23-34, 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000, Taipei, Taiwan, Province of China, 12/18/00. https://doi.org/10.1007/3-540-40996-3_3

Bose P, Czyzowicz J, Gąsieniec L, Kranakis E, Krizanc D, Pelc A et al. Strategies for hotlink assignments. In Lee DT, Teng SH, Teng SH, editors, Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Springer Verlag. 2000. p. 23-34. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-40996-3_3

Bose, Prosenjit ; Czyzowicz, Jurek ; Gąsieniec, Leszek et al. / Strategies for hotlink assignments. Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. editor / D.T. Lee ; Shang-Hua Teng ; Shang-Hua Teng. Springer Verlag, 2000. pp. 23-34 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3168ee8a54a8422c834687173401b26b,

title = "Strategies for hotlink assignments",

abstract = "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.",

author = "Prosenjit Bose and Jurek Czyzowicz and Leszek G{\c a}sieniec and Evangelos Kranakis and Danny Krizanc and Andrzej Pelc and Martin, {Miguel Vargas}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 ; Conference date: 18-12-2000 Through 20-12-2000",

year = "2000",

doi = "10.1007/3-540-40996-3_3",

language = "English (US)",

isbn = "3540412557",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "23--34",

editor = "D.T. Lee and Shang-Hua Teng and Shang-Hua Teng",

booktitle = "Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings",

}

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

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

PB - Springer Verlag

T2 - 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000

Y2 - 18 December 2000 through 20 December 2000

ER -

Strategies for hotlink assignments

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this