Linear-Time Pointer-Machine Algorithms for Path-Evaluation

Problems on Trees and Graphs

Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers,

Robert E. Tarjan and Jeffery R. Westbrook

Abstract

We present algorithms running in linear time on a pointer machine for a collection of problems, each of which either directly or indirectly requires the evaluation of a function defined on paths in a tree.  These problems previously had linear-time algorithms, but only for a random-access machine (RAM); the best pointer-machine algorithms were non-linear by an inverse-Ackermann-function factor. Our algorithms are also simpler, in some cases substantially, than the previous linear-time RAM algorithms.  Our improvements come primarily from three new ideas: a refined analysis of path compression that gives a linear bound if the compressions favour certain nodes, pointer-based radix sort as a replacement for table-based methods, and a more careful partitioning of a tree into easily-managed parts.  Our algorithms compute nearest common ancestors off-line, verify and construct minimum spanning trees, do interval analysis on a flowgraph, find the dominators of a flowgraph, and build the component tree of a weighted tree.