Assigning Bookmarks in Perfect Binary Trees

Abstract

Consider a tree $T=(V,E)$ with root $r\in 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\le \sqrt{N+1}$.