Sequential And Parallel Algorithms For The Nca Problem On Pure Pointer Machines

We present a simple, arithmetic-free, efficient scheme to compress trees maintaining theNCAinformation.We use this compression scheme to provide an O(n + q lg lg n) solution for solving the NCA problem on Pure Pointer Machines (PPMs)—i.e., pointer machines with no arithmetic capabilities—in both the static and dynamic case, where n is the number of add-leaf/delete operations and q is the number of NCA queries. This solution is optimal.We also extend the solution to a parallel pointer machine algorithm. The algorithm assumes that the tree T is known in advance and it requires O(lg n) parallel time and O(n) processors for pre-processing where n is the number of nodes in the tree. Thereafter, it can answer any NCA query in O(lg lg n) time using a single processor. To our knowledge, this is the best known parallel pointer machine algorithm for the NCA problem. Our NCA algorithm requires an efficient parallel solution of the temporal precedence problem [Ranjan et al., The temporal precedence problem, Algorithmica 28 (2000) 288–306].We provide an efficient parallel pointer machine algorithm to solve this problem as well.