Name
Abstract | ||
|---|---|---|
Consider a tree T = (V, E) with root r is an element of V and |V| = N. Let p(v) be the probability that a user wants to access node v. A bookmark is an additional link from r to any other node of T. We want to add k bookmarks to T, so as to minimize the expected access cost from r, measured by the average length of the shortest path. We present a characterization of an optimal assignment of k bookmarks in a perfect binary tree with uniform probability distribution of access and k < root N+1. |
Year | Venue | Keywords |
|---|---|---|
2007 | ARS COMBINATORIA | binary tree |
Field | DocType | Volume |
Scapegoat tree,Combinatorics,Self-balancing binary search tree,Optimal binary search tree,Binary tree,Theoretical computer science,Weight-balanced tree,Random binary tree,Ternary search tree,Mathematics,Binary search tree | Journal | 82 |
ISSN | Citations | PageRank |
0381-7032 | 4 | 0.45 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jurek Czyzowicz | 1 | 778 | 74.35 |
| Evangelos Kranakis | 2 | 3107 | 354.48 |
| Danny Krizanc | 3 | 1778 | 191.04 |
| Andrzej Pelc | 4 | 3416 | 246.55 |
| Miguel Vargas Martin | 5 | 106 | 24.08 |