On Finding Lowest Common Ancestors in Trees

DOI10.1137/0205011MaRDI QIDQ4089769zbMATH OpenOpenAlexFDO

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)

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

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)