Lowest common ancestors in trees and directed acyclic graphs

2005/09/17 by Michael A. Bender, Martín Farach-Colton, Martı́n Farach-Colton +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics #Directed acyclic graph #Genealogy #Graph Theory and Algorithms #History #Mathematics

paper · doi:10.1016/j.jalgor.2005.08.001

openalex publication_date 2005/09/17 · crossref created 2005/09/17 · crossref issued 2005/11/01 · crossref published 2005/11/01 · crossref published-print 2005/11/01 · crossref deposited 2019/01/22 · openalex created_date 2025/10/10 · crossref indexed 2026/07/03 · openalex updated_date 2026/07/22

Citations

• Fast Algorithms for Finding Nearest Common Ancestors
• Applications of Path Compression on Balanced Trees
• A linear-time algorithm for a special case of disjoint set union
• Finding level-ancestors in trees
• The LCA Problem Revisited

Cited by

• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Lowest common ancestor [wikipedia]