Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment

2004/04/29 by Stephen Alstrup, Cyril Gavoille, Haim Kaplan +1 · 1 citation
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Ancestor #Combinatorics #Complexity and Algorithms in Graphs #Computer network #Computer science #Constant (computer programming) #Data structure #Distributed systems and fault tolerance #Geography #Mathematics #Node (physics) #Routing (electronic design automation) #Simple (philosophy) #Theoretical computer science #Time complexity #Tree (set theory)

paper · doi:10.1007/s00224-004-1155-5

openalex publication_date 2004/04/29 · crossref created 2004/04/29 · crossref issued 2004/05/01 · crossref published 2004/05/01 · crossref published-print 2004/05/01 · crossref deposited 2019/05/24 · openalex created_date 2025/10/10 · crossref indexed 2026/02/13 · openalex updated_date 2026/07/28

Citations

• Fast Algorithms for Finding Nearest Common Ancestors
• A data structure for dynamic trees
• Applications of Path Compression on Balanced Trees
• Finding level-ancestors in trees
• Optimal suffix tree construction with large alphabets
• Depth-First Search and Linear Graph Algorithms
• The LCA Problem Revisited
• A randomized linear-time algorithm to find minimum spanning trees
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Scaling and related techniques for geometry problems
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Recursive Star-Tree Parallel Data Structure

Cited by

• Lowest common ancestor [wikipedia]