Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs

Simple item page
dc.creatorBuchsbaum, Adam L.
dc.creatorGeorgiadis, Loukas
dc.creatorKaplan, Haim
dc.creatorRogers, Anne
dc.creatorTarjan, Robert E.
dc.creatorWestbrook, Jeffery R.
dc.date2002-07-15
dc.date2006-11-14
dc.date.accessioned2026-07-07T06:34:55Z
dc.date.available2026-07-07T06:34:55Z
dc.descriptionWe 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.
dc.description41 pages; 10 figures; 1 table; 65 references. This work is partially covered by the extended abstracts, ``Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators,'' Proc. 30th ACM Symp. on Theory of Computing, pp. 279-888, 1998, and ``Finding Dominators Revisited,'' Proc. 15th ACM-SIAM Symp. on Discrete Algorithms, pp. 862-871, 2004
dc.identifierhttps://arxiv.org/abs/cs/0207061
dc.identifierhttp://arxiv.org/abs/cs/0207061
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/99666
dc.subjectData Structures and Algorithms
dc.subjectD.3.4; E.1; F.1.1; F.2.2; G.2.2
dc.titleLinear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs
dc.typetext

Files

Collections

arXiv