Sequential and parallel algorithms for the NCA problem on pure pointer machines

DOI10.1016/J.TCS.2005.10.040MaRDI QIDQ818121zbMATH OpenOpenAlexFDO

Authors A. Dal Palú, Enrico Pontelli, Desh Ranjan

Publication date 24 March 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.10.040

zbMATH Keywords

dynamic data structuresnearest common ancestorpointer machines

Mathematics Subject Classification ID

Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• An Optimal Algorithm for Finding NCA on Pure Pointer Machines
• Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
• scientific article; zbMATH DE number 2086234
• scientific article; zbMATH DE number 4047158
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees

Cites work

• A class of algorithms which require nonlinear time to maintain disjoint sets
• A linear-time algorithm for a special case of disjoint set union
• A simple optimal solution for the temporal precedence problem on pure pointer machines
• A universal interconnection pattern for parallel computers
• Data structures for order-sensitive predicates in parallel nondeterministic systems
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 2086234 (Why is no real title available?)
• scientific article; zbMATH DE number 1305412 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1775413 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Logic Programming
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On pointers versus addresses
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees
• Optimal solutions for the temporal precedence problem
• Parallel pointer machines
• Parallelism in random access machines
• The nearest common ancestor in a dynamic tree
• The temporal precedence problem

Cited in

(2)

• An Optimal Algorithm for Finding NCA on Pure Pointer Machines
• Computational Issues in Exploiting Dependent And-Parallelism in Logic Programming: Leftness Detection in Dynamic Search Trees

This page was built for publication: Sequential and parallel algorithms for the NCA problem on pure pointer machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q818121)