On Finding Lowest Common Ancestors in Trees

DOI10.1137/0205011zbMATH Open0325.68018OpenAlexW2004116976MaRDI QIDQ4089769FDOQ4089769

Authors: A. V. Aho, John Hopcroft, Jeffrey D. Ullman 

Publication date: 1976

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0205011

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited In (20)

• Finding dominators via disjoint set union
• Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
• Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
• Strong articulation points and strong bridges in large scale graphs
• New common ancestor problems in trees and directed acyclic graphs
• Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint
• A linear-time algorithm for a special case of disjoint set union
• Parallel dynamic lowest common ancestors
• A data structure for dynamic trees
• Ranking arborescences in O(Km log n) time
• On computing distances between leaves in a complete tree
• Algorithms for weighted matching generalizations. II: \(f\)-factors and the special case of shortest paths
• On pattern matching with \(k\) mismatches and few don't cares
• Searching and encoding for infinite ordered sets
• Complete edge-colored permutation graphs
• A Path Cover Technique for LCAs in Dags
• Decomposition of triply rooted trees
• The nearest common ancestor in a dynamic tree
• A \(\min\)-\(\max\) relation in flowgraphs and some applications
• The longest common substring problem

This page was built for publication: On Finding Lowest Common Ancestors in Trees

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