Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators.

Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook

Browse the full STOC paper archive.