Fast Algorithms for Finding Nearest Common Ancestors

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

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)

Related Items

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, Parallel string matching with k mismatches, Computing on a free tree via complexity-preserving mappings, Rectilinear short path queries among rectangular obstacles, A note on finding compact sets in graphs represented by an adjacency list, An \(O(ND)\) difference algorithm and its variations, A simpler minimum spanning tree verification algorithm, Data structures and algorithms for approximate string matching, A log log n data structure for three-sided range queries, Fast string matching with k differences, Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species, An efficient algorithm for sequence comparison with block reversals, The suffix tree of a tree and minimizing sequential transducers, Drawing \(c\)-planar biconnected clustered graphs, Extracting powers and periods in a word from its runs structure, Efficient seed computation revisited, A scalable approach to computing representative lowest common ancestor in directed acyclic graphs, The longest common extension problem revisited and applications to approximate string searching, A faster computation of all the best swap edges of a shortest paths tree, Exact algorithms for computing the tree edit distance between unordered trees, Linear-time superbubble identification algorithm for genome assembly, Recursive voids for identifying a nonconvex boundary of a set of points in the plane, Cache oblivious algorithms for the RMQ and the RMSQ problems, Traveling salesman problem heuristics: leading methods, implementations and latest advances, Linear-time construction of two-dimensional suffix trees, Computing runs on a general alphabet, Fast layout computation of clustered networks: algorithmic advances and experimental analysis, Efficient retrieval of approximate palindromes in a run-length encoded string, Improved algorithms for the range next value problem and applications, Ramified rectilinear polygons: coordinatization by dendrons, String matching with weighted errors, Efficient algorithms for local ranking, Recognizing breadth-first search trees in linear time, Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph, The saga of minimum spanning trees, All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time, Finding best swap edges minimizing the routing cost of a spanning tree, An efficient algorithm for some tree matching problems, A scalable parallelization of the gene duplication problem, Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses, Alphabet-independent algorithms for finding context-sensitive repeats in linear time, A note on the longest common compatible prefix problem for partial words, Improved space-time tradeoffs for approximate full-text indexing with one edit error, Linear-time version of Holub's algorithm for morphic imprimitivity testing, On the fixed parameter tractability of agreement-based phylogenetic distances, Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence, The 2-radius and 2-radiian problems on trees, Transitions in geometric minimum spanning trees, Computing the coarseness with strips or boxes, Computing the center of uncertain points on tree networks, On Cartesian trees and range minimum queries, Stacks, queues, and deques with order-statistic operations, On space efficient two dimensional range minimum data structures, Faster approximate string matching for short patterns, Two-dimensional dictionary matching, Randomized range-maxima in nearly-constant parallel time, Fitting a step function to a point set, Testing convexity properties of tree colorings, Faster query algorithms for the text fingerprinting problem, Cache-oblivious index for approximate string matching, Bounded hairpin completion, Building species trees from larger parts of phylogenomic databases, A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings, Range mode and range median queries in constant time and sub-quadratic space, A survey on tree edit distance and related problems, Finding the upper envelope of n line segments in O(n log n) time, An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation, New common ancestor problems in trees and directed acyclic graphs, Faster algorithms for computing the R* consensus tree, Fast algorithms for computing the tripartition-based distance between phylogenetic networks, A linear-time algorithm for the geodesic center of a simple polygon, Ramsey partitions and proximity data structures, A decomposition theorem and two algorithms for reticulation-visible networks, Fast algorithms for computing tree LCS, Center location problems on tree graphs with subtree-shaped customers, Efficient algorithms for two generalized 2-median problems and the group median problem on trees, The Level-Ancestor problem on pure pointer machines, Moving a disc between polygons, Improved algorithms for the multicut and multiflow problems in rooted trees, Real two dimensional scaled matching, A uniform approach to semi-dynamic problems on digraphs, Matching subsequences in trees, A fast and simple Steiner routing heuristic, Data compression for proof replay, Two flow network simplification algorithms, A linear-time algorithm for a special case of disjoint set union, On rectilinear link distance, Succinct indices for path minimum, with applications, Optimal parallel verification of minimum spanning trees in logarithmic time, When can you fold a map?, Approximating geometric bottleneck shortest paths, Efficient algorithms for the minmax regret path center problem with length constraint on trees, Tight lower bounds for the longest common extension problem, Space-efficient indexes for forbidden extension queries, Faster algorithms for finding lowest common ancestors in directed acyclic graphs, Approximating points by a piecewise linear function, Succinct representations of weighted trees supporting path queries, Generalized LCS, Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor, The heaviest induced ancestors problem: better data structures and applications, On the range maximum-sum segment query problem, Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems, Computing longest common extensions in partial words, A robust model for finding optimal evolutionary tree, Non-shared edges and nearest neighbor interchanges revisited, Computing \(k\)-centers of uncertain points on a real line, Succinct 2D dictionary matching, Tree structure for distributive lattices and its applications, Fingerprints in compressed strings, Arboral satisfaction: recognition and LP approximation, Efficient testing and matching of deterministic regular expressions, Finding all minimum cost flows and a faster algorithm for the \(K\) best flow problem, On finding the Adams consensus tree, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Longest common substring with approximately \(k\) mismatches, Best match graphs, An introduction to the Ribe program, Dynamic orthogonal range queries in OLAP., An improved algorithm for the minmax regret path center problem on trees, Drawing trees with perfect angular resolution and polynomial area, Fast arc-annotated subsequence matching in linear space, Faster swap edge computation in minimum diameter spanning trees, The nearest colored node in a tree, Motif trie: an efficient text index for pattern discovery with don't cares, Efficient algorithms for shortest partial seeds in words, The complexity of the locally connected spanning tree problem, Dynamic planar range skyline queries in log logarithmic expected time, 2-dimensional palindromes with \(k\) mismatches, Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs, Constructing the R* consensus tree of two trees in subcubic time, Generalized substring compression, Dynamic 3-sided planar range queries with expected doubly-logarithmic time, Time-space trade-offs for longest common extensions, Computing the rooted triplet distance between galled trees by counting triangles, A few logs suffice to build (almost) all trees. II, The lowest common ancestor problem on a tree with an unfixed root, Multidimensional segment trees can do range updates in poly-logarithmic time, Building Cartesian trees from free trees with \(k\) leaves, Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs, Computing longest palindromic substring after single-character or block-wise edits, Linear time algorithm for the longest common repeat problem, Engineering a combinatorial Laplacian solver: lessons learned, Finding maximal 2-dimensional palindromes, A simple linear-space data structure for constant-time range minimum query, Query-point visibility constrained shortest paths in simple polygons, Maximum agreement and compatible supertrees, Efficient vertex-label distance oracles for planar graphs, Simultaneous embedding: edge orderings, relative positions, cutvertices, A \(\min\)-\(\max\) relation in flowgraphs and some applications, Efficient counting of square substrings in a tree, Dynamic relative compression, dynamic partial sums, and substring concatenation, Reporting and counting maximal points in a query orthogonal rectangle, String indexing for patterns with wildcards, Join-reachability problems in directed graphs, A new framework for addressing temporal range queries and some preliminary results, An improved algorithm for tree edit distance with applications for RNA secondary structure comparison, On the restricted 1-Steiner tree problem, \(L_{1}\) shortest path queries in simple polygons, Fast parallel and serial multidimensional approximate array matching, Internal dictionary matching, Indexing weighted sequences: neat and efficient, Efficient pattern matching in elastic-degenerate strings, A faster approximation algorithm for the Steiner tree problem in graphs, A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP, The nearest common ancestor in a dynamic tree, Quickest visibility queries in polygonal domains, Analytical description of digital intersections: minimal parameters and multiscale representation, Multiple-edge-fault-tolerant approximate shortest-path trees, Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane, Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences, Range minimum queries in minimal space, A data structure for dynamic trees, On the restricted \(k\)-Steiner tree problem, One-way and round-trip center location problems, Decomposition algorithms for the tree edit distance problem, Distances in benzenoid systems: Further developments, Planarity of streamed graphs, Quasi-linear algorithms for the topological watershed, Optimal centrality computations within bounded clique-width graphs, The fast algorithm for online \(k\)-server problem on trees, Parallel preprocessing for path queries without concurrent reading., Approximate periodicity, Geometric biplane graphs. II: Graph augmentation, An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, Computing the \(K\)-terminal reliability of directed path graphs, Disconnectivity and relative positions in simultaneous embeddings, An optimal data structure to handle dynamic environments in non-deterministic computations