Efficient parallel algorithms for tree-related problems using the parentheses matching strategy

Although several strategies have been developed for designing efficient parallel algorithms, there is still a need for new strategies so that efficient or simple solutions can be obtained for broader classes of problems. We establish a new design strategy, called parallel parentheses matching (PPM), by solving a number of problems related to trees. With this strategy, a given problem is first converted into an equivalent parentheses matching problem the solution of which finally leads to the desired solution of the original problem. The PPM strategy is applied to solve various bottom-up tree computation problems such as heights of the nodes of a tree, extreme valves in subtrees, and lowest common ancestor. Furthermore, elegant algorithms are presented for the tree contraction problem and balancing binary trees, thus demonstrating the versatility of our approach