Fast Algorithms for Finding Nearest Common Ancestors
From MaRDI portal
Publication:3319776
DOI10.1137/0213024zbMath0535.68022OpenAlexW2011999472WikidataQ29029956 ScholiaQ29029956MaRDI QIDQ3319776
Dov Harel, Robert Endre 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
treegraph algorithmpointer machinesrandom access machinenearest common ancestorinverse Ackermann's function
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)
Related Items (only showing first 100 items - show all)
Parallel dynamic lowest common ancestors ⋮ Optimal pointer algorithms for finding nearest common ancestors in dynamic trees ⋮ Linear-time heuristics for minimum weight rectangulation ⋮ Time-Space Trade-Offs for Longest Common Extensions ⋮ Faster enumeration of all spanning trees of a directed graph ⋮ Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs ⋮ Path-Fault-Tolerant Approximate Shortest-Path Trees ⋮ A Faster Computation of All the Best Swap Edges of a Tree Spanner ⋮ Optimal Algorithms for Running Max and Min Filters on Random Inputs ⋮ Inductive computations on graphs defined by clique-width expressions ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Longest Common Extensions in Trees ⋮ Longest Common Extensions in Sublinear Space ⋮ Range Minimum Query Indexes in Higher Dimensions ⋮ Internal shortest absent word queries in constant time and linear space ⋮ A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs ⋮ Finding cores of limited length ⋮ Complete edge-colored permutation graphs ⋮ Tight bound for the number of distinct palindromes in a tree ⋮ Checking whether a word is Hamming-isometric in linear time ⋮ String Indexing with Compressed Patterns ⋮ Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Shortest beer path queries in outerplanar graphs ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Fast Algorithms for Computing Tree LCS ⋮ Partial and simultaneous transitive orientations via modular decompositions ⋮ Geometric hitting set for line-constrained disks ⋮ Dynamic convex hulls under window-sliding updates ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ Efficient Algorithms for SNP Haplotype Block Selection Problems ⋮ Reconstructing parameterized strings from parameterized suffix and LCP arrays ⋮ A Path Cover Technique for LCAs in Dags ⋮ Finding diameter-reducing shortcuts in trees ⋮ Reconstructing parameterized strings from parameterized suffix and LCP arrays ⋮ Unnamed Item ⋮ The longest common substring problem ⋮ Double string tandem repeats ⋮ Fitting a Step Function to a Point Set ⋮ Faster Swap Edge Computation in Minimum Diameter Spanning Trees ⋮ Compact and localized distributed data structures ⋮ Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint ⋮ Strong Steiner Tree Approximations in Practice ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Secure Authenticated Comparisons ⋮ Shortest-Path Queries in Geometric Networks ⋮ FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING ⋮ PARENT QUERIES OVER DYNAMIC BALANCED PARENTHESIS STRINGS ⋮ Spaces, Trees, and Colors ⋮ Forty Years of Text Indexing ⋮ Unnamed Item ⋮ Optimal parallel suffix tree construction ⋮ Euler is standing in line dial-a-ride problems with precedence-constraints ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ An improved algorithm for diameter-optimally augmenting paths in a metric space ⋮ Unnamed Item ⋮ A simpler minimum spanning tree verification algorithm ⋮ A linear-space data structure for range-LCP queries in poly-logarithmic time ⋮ Compressed indexes for approximate string matching ⋮ Approximation algorithms for graph augmentation ⋮ Fast incremental planarity testing ⋮ A linear-time algorithm for radius-optimally augmenting paths in a metric space ⋮ From Gene Trees to Species Trees through a Supertree Approach ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ Covering uncertain points in a tree ⋮ Range LCP ⋮ Some Remarks on Superposition Based on Watson-Crick-Like Complementarity ⋮ A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners ⋮ Some Results for Elementary Operations ⋮ A Linear-Time Algorithm for Seeds Computation ⋮ What’s Behind Blast ⋮ Dynamic algorithms for graphs of bounded treewidth ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Small-space LCE data structure with constant-time queries ⋮ Faster Approximate Diameter and Distance Oracles in Planar Graphs ⋮ Orthogonal Range Searching for Text Indexing ⋮ Array Range Queries ⋮ PARALLEL RANGE MINIMA ON COARSE GRAINED MULTICOMPUTERS ⋮ Efficient maximum matching algorithms for trapezoid graphs ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ How to Keep an Eye on Small Things ⋮ Unnamed Item ⋮ Longest Lyndon Substring After Edit ⋮ Non-Overlapping Indexing - Cache Obliviously ⋮ Longest substring palindrome after edit ⋮ The Heaviest Induced Ancestors Problem Revisited ⋮ Sequential and parallel algorithms for the NCA problem on pure pointer machines ⋮ New algorithms for the LCA problem and the binary tree reconstruction problem ⋮ Finding level-ancestors in trees ⋮ Finding lowest common ancestors in arbitrarily directed trees ⋮ Ray shooting in polygons using geodesic triangulations ⋮ Unit-cost pointers versus logarithmic-cost addresses ⋮ Pattern matching in a digitized image ⋮ A constant update time finger search tree ⋮ Common intervals of trees ⋮ Online timestamped text indexing ⋮ Longest common extensions in trees ⋮ Order-preserving indexing ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Almost fully-parallel parentheses matching
This page was built for publication: Fast Algorithms for Finding Nearest Common Ancestors
