Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs
<|reference_start|>Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs: We present algorithms that run in linear time on pointer machines 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 random-access machines (RAMs); the best pointer-machine algorithms were super-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 favor certain nodes, a 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.<|reference_end|>
@article{buchsbaum2002linear-time,
    title={Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on
  Trees and Graphs},
    author={Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert
  E. Tarjan, and Jeffery R. Westbrook},
    journal={arXiv preprint arXiv:cs/0207061},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0207061},
    primaryClass={cs.DS}
}