Searching in Trees, Series-Parallel and Interval Orders

Abstract

Linial and Saks [2] have shown that $O(\log N)$ evaluations of an order preserving map $f:p \to \mathbb{R}$ are necessary and sufficient to determine whether $\alpha \in f(P)$, where N is the number of ideals of N and $\alpha \in \mathbb{R}$ is a given real number. In this paper, we investigate the problem of how to perform the evaluations so that Linial and Saks’ bound is guaranteed, and solve the problem for the classes of interval and series-parallel orders and hence, in particular, for rooted trees. We observe that the greedy-type binary search algorithm, which is optimal for chains, already need not be optimal for general rooted trees. We furthermore discuss the computational complexity of the general search problem and obtain results indicating that the general problem might be hard.