Computer Science – Data Structures and Algorithms
Scientific paper
2002-07-15
Computer Science
Data Structures and Algorithms
41 pages; 10 figures; 1 table; 65 references. This work is partially covered by the extended abstracts, ``Linear-Time Pointer-
Scientific paper
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.
Buchsbaum Adam L.
Georgiadis Loukas
Kaplan Haim
Rogers Anne
Tarjan Robert E.
No associations
LandOfFree
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-375979