Consider a tree T = (V, E) with root r ∈ 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 ≤ √N + 1.

Ars Combinatoria
School of Computer Science

Czyzowicz, J. (Jurek), Kranakis, E, Krizanc, D. (Danny), Pelc, A. (Andrzej), & Martin, M.V. (Miguel Vargas). (2007). Assigning bookmarks in perfect binary trees. Ars Combinatoria, 82, 165–179.