3
Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size $O(n)$ and query time $O(1)$. This is optimal also for trees (e.g., if the input is a star graph, then you need to know the orientation of every one of the $n-1$ edges).
[1] Holm, Jacob, Eva Rotenberg, and Mikkel Thorup. "Planar ...
2
There are several possible ways to answer this question. On the one hand, it is often assumed in distributed computing that the nodes have unbounded local computational power, because this point of view makes it possible to focus on the inherent difficulties of the distributed aspects. In such cases, lower bounds related to classical (i.e. sequential) ...
Only top voted, non community-wiki answers of a minimum length are eligible
