On Finding Lowest Common Ancestors in Trees

DOI10.1137/0205011zbMath0325.68018OpenAlexW2004116976MaRDI QIDQ4089769

A. V. Aho, Jeffrey D. Ullman, John E. Hopcrofts

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

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

Related Items

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