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 \leq \sqrt{N + 1}\).