Fast Algorithms for Finding Nearest Common Ancestors

DOI10.1137/0213024zbMATH Open0535.68022OpenAlexW2011999472WikidataQ29029956 ScholiaQ29029956MaRDI QIDQ3319776FDOQ3319776

Authors: Dov Harel, Robert E. Tarjan 

Publication date: 1984

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

Full work available at URL: https://semanticscholar.org/paper/8867d059dda279b1aed4a0301e4e46f9daf65174

Recommendations

• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Near-optimal labeling schemes for nearest common ancestors
• scientific article; zbMATH DE number 4064469
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Fast Lowest Common Ancestor Computations in Dags
• A Data Structure for Nearest Common Ancestors with Linking
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• Fast smallest lowest common ancestor computation based on stable match
• Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees

zbMATH Keywords

treegraph algorithmpointer machinesrandom access machinenearest common ancestorinverse Ackermann's function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Cited In (only showing first 100 items - show all)

• Efficient seed computation revisited
• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Approximating geometric bottleneck shortest paths
• Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
• 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
• Transitions in geometric minimum spanning trees
• Improved space-time tradeoffs for approximate full-text indexing with one edit error
• A fast and simple Steiner routing heuristic
• Computing on a free tree via complexity-preserving mappings
• A survey on tree edit distance and related problems
• Finding lowest common ancestors in arbitrarily directed trees
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
• Two flow network simplification algorithms
• Efficient retrieval of approximate palindromes in a run-length encoded string
• Improved algorithms for the range next value problem and applications
• An efficient algorithm for some tree matching problems
• Faster Swap Edge Computation in Minimum Diameter Spanning Trees
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Efficient algorithms for local ranking
• Range mode and range median queries in constant time and sub-quadratic space
• Center location problems on tree graphs with subtree-shaped customers
• A linear-time algorithm for a special case of disjoint set union
• Title not available (Why is that?)
• Longest common extensions in trees
• Online timestamped text indexing
• Longest common extensions in trees
• Order-preserving indexing
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Extracting powers and periods in a word from its runs structure
• A few logs suffice to build (almost) all trees. II
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• The longest common extension problem revisited and applications to approximate string searching
• Array range queries
• A data structure for dynamic trees
• A robust model for finding optimal evolutionary tree
• On space efficient two dimensional range minimum data structures
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• Range LCP
• Ramsey partitions and proximity data structures
• Ray shooting in polygons using geodesic triangulations
• Computing runs on a general alphabet
• Faster query algorithms for the text fingerprinting problem
• Compressed indexes for approximate string matching
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• Real two dimensional scaled matching
• Maximum agreement and compatible supertrees
• The saga of minimum spanning trees
• An \(O(ND)\) difference algorithm and its variations
• Decomposition algorithms for the tree edit distance problem
• The suffix tree of a tree and minimizing sequential transducers
• Finding the upper envelope of n line segments in O(n log n) time
• A simpler minimum spanning tree verification algorithm
• Traveling salesman problem heuristics: leading methods, implementations and latest advances
• Fast algorithms for computing the tripartition-based distance between phylogenetic networks
• Succinct representations of weighted trees supporting path queries
• Finding level-ancestors in trees
• Two-dimensional dictionary matching
• Ramified rectilinear polygons: coordinatization by dendrons
• Orthogonal range searching for text indexing
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Finding best swap edges minimizing the routing cost of a spanning tree
• Bounded hairpin completion
• Longest common extensions in sublinear space
• One-way and round-trip center location problems
• A Path Cover Technique for LCAs in Dags
• The nearest common ancestor in a dynamic tree
• Data compression for proof replay
• Tree structure for distributive lattices and its applications
• Optimal parallel verification of minimum spanning trees in logarithmic time
• Generalized LCS
• Drawing trees with perfect angular resolution and polynomial area
• Generalized substring compression
• A \(\min\)-\(\max\) relation in flowgraphs and some applications
• Time-space trade-offs for longest common extensions
• Dynamic algorithms for graphs of bounded treewidth
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• An introduction to the Ribe program
• Efficient maximum matching algorithms for trapezoid graphs
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• Distances in benzenoid systems: Further developments
• Recognizing breadth-first search trees in linear time
• Efficient algorithms for the minmax regret path center problem with length constraint on trees
• Succinct indices for path minimum, with applications
• When can you fold a map?
• Faster approximate string matching for short patterns
• An improved algorithm for the minmax regret path center problem on trees
• Common intervals of trees
• Faster swap edge computation in minimum diameter spanning trees
• Fast incremental planarity testing
• Fitting a step function to a point set
• Testing convexity properties of tree colorings
• Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
• Fast string matching with k differences
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• Linear time algorithm for the longest common repeat problem

This page was built for publication: Fast Algorithms for Finding Nearest Common Ancestors

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